Question: How would you check if a binary tree is balanced?
Answer: A tree is considered balanced when the difference between the min depth and max depth does not exceed 1.
Recursive algorithms always work well on trees, so here’s some code.
int min_depth( Node * root ) {
if( !root ) {
return 0;
}
return 1 + min( min_depth( root->left ),
min_depth( root->right ));
}
int max_depth( Node * root ) {
if( !root ) {
return 0;
}
return 1 + max( max_depth( root->left ),
max_depth( root->right ));
}
bool is_balanced( Node * root ) {
return ( max_depth( root ) - min_depth( root ) ) <= 1
}
Simple enough, right? Spread the word on Twitter and Digg!
mindepth calculation is wrong. Imagine a tree with right branches having only right nodes and left branches having only left nodes. The above recursion will always return 2.
int mindepth(struct tree *curr)
{
if (curr == NULL)
return 0;
int leftdepth = mindepth(curr->left);
int rightdepth = mindepth(curr->right);
if (leftdepth != 0 && rightdepth != 0)
return 1+(min(leftdepth, rightdepth));
else if (leftdepth == 0)
return 1+ rightdepth;
else if (rightdepth == 0)
return 1+ leftdepth;
}
Typically the definition of balanced means that every node in the tree is balanced and not just the root. If you have a tree which has 100 nodes to the left, all of which are left children and 100 node to the right, all of which are right children, the root is balanced but most other nodes are not.
Disregarding efficiency, this is easy to fix in the proposed solution. Just change the return expression of is_balanced to be what it already is && is_balanced(leftChild) && isbalanced(rightChild)
I wish I could delete my old comment.. was going to go to bed, but that seg fault was really bothering me
Here is the revised code.
#include
#include
#ifndef max
#define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
#endif
#ifndef min
#define min( a, b ) ( ((a) right, &rightmin, &rightmax);
minmax_depth(root->left, &leftmin, &leftmax);
*min = 1 + min(leftmin, rightmin);
*max = 1 + max(leftmax, rightmax);
return;
}
bool is_balanced( Node *root) {
int min, max;
min = max = 0;
minmax_depth(root, &min, &max);
return (max – min) <= 1;
}
void main() {
Node *head = NULL, *tmp = NULL;
int i;
for (i = 0; i left = NULL;
tmp->right = head;
tmp->data = i;
head = tmp;
}
if(!is_balanced(head)) {
printf(“Should be balanced… but isn’t\n”);
} else {
printf(“Balanced, as expected\n”);
}
if ((tmp = malloc(sizeof(Node))) == NULL) {abort();};
tmp->left = NULL;
tmp->right = head;
tmp->data = i;
head = tmp;
if(is_balanced(head)) {
printf(“Shouldn’t be balanced… but is\n”);
} else {
printf(“Unbalanced, as expected\n”);
}
}
I haven’t touched C in quite a few years, but here is what I came up with. This seg faults at line 24, so don’t quote me on it. But the algorithm should hold true.
#include
#include
#include “Node.h”
#ifndef max
#define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
#endif
#ifndef min
#define min( a, b ) ( ((a) right, &rightmin, &rightmax);
minmax_depth(root->left, &leftmin, &leftmax);
*min = 1 + min(leftmin, rightmin);
*max = 1 + max(leftmax, rightmax);
return;
}
bool is_balanced( Node *root) {
int min, max;
min = max = 0;
minmax_depth(root, &min, &max);
return (max – min) > 0;
}
void main() {
printf(“Initializing”);
Node *head, *tmp = NULL;
int i;
printf(“Initializing”);
for (i = 0; i right = head;
head = tmp;
}
if(is_balanced(head)) {
printf(“Shouldn’t be balanced… but is”);
}
}
Could you return both min and max values in the same function / traversal ?