# How will you find if a binary tree is fully balanced?

A Bhattacharya
Ranch Hand
Posts: 125
I gave the following answer in the telephone interview:
boolean isBalanced(Tree *t,int *height)
{
if(t==NULL)
{
*height = 0;
return true;
}
int leftheight,rightheight;
boolean leftBalanced = isBalanced(t->lptr,&leftheight)
boolean rightBalanced = isBalanced(t->rptr,&rightheight)
bolean balanced = leftBalanced && rightBalanced && abs(leftheight-rightheight)<=1
*height = 1+max(leftheight,rightheight)
return balanced
}

I didn't dictate line by line but explained the above logic in words. I said the time complexity is O(n) where n is the no of nodes in the tree. But he insisted like idiot that the complexity is O(n^2) and was saying that for each subtree we will have to process all the nodes in the subtree but I kept saying that we process each node exactly once. I think he either didn't understand my answer properly or was stuck up with an inefficient algorithm he had in mind. My question is, is my algorithm correct or not?

Campbell Ritchie
Sheriff
Posts: 50656
83
Difficult to be sure, and it is some time since I had to write any C code but I think your algorithm is OK. And I think you are right about linear complexity.

Anybody else? Not really my sphere of expertise.

Rob Spoor
Sheriff
Posts: 20707
68
You only inspect each node once, you yes, it is O(n). The reason the other guy may be confused is the order of inspecting - that's not linear.

Brian Cole
Author
Ranch Hand
Posts: 911
1
Originally posted by A Bhattacharya:
I gave the following answer in the telephone interview:
boolean isBalanced(Tree *t,int *height)
{
if(t==NULL)
{
*height = 0;
return true;
}
int leftheight,rightheight;
boolean leftBalanced = isBalanced(t->lptr,&leftheight)
boolean rightBalanced = isBalanced(t->rptr,&rightheight)
bolean balanced = leftBalanced && rightBalanced && abs(leftheight-rightheight)<=1
*height = 1+max(leftheight,rightheight)
return balanced
}

I didn't dictate line by line but explained the above logic in words. I said the time complexity is O(n) where n is the no of nodes in the tree. But he insisted like idiot that the complexity is O(n^2) and was saying that for each subtree we will have to process all the nodes in the subtree but I kept saying that we process each node exactly once. I think he either didn't understand my answer properly or was stuck up with an inefficient algorithm he had in mind. My question is, is my algorithm correct or not?

First, the algorithm is definitely linear in the number of nodes. Not sure what he was thinking to claim O(n^2).

Second, I'm not sure it's correct, depending on what exactly we mean by "fully balanced." Consider the tree ((a(bc))((de)((fg)h))). The left subtree (a(bc)) is balanced with depth 2. The right subtree ((de)((fg)h)) is balanced with depth 3. However leaf a has depth 2 while leaf f has depth 4.

[edit: See below for a fantasmic ASCII-graphic pictoral representation. Also, I may be quoting depth values one lower than your algorithm's, but I believe my meaning is clear.]
[ May 08, 2008: Message edited by: Brian Cole ]

A Bhattacharya
Ranch Hand
Posts: 125
Brian
I'm not able to understand the tree notation you are using. Can you pictorially depict your tree? thanks for taking the trouble.

Brian Cole
Author
Ranch Hand
Posts: 911
1
Originally posted by A Bhattacharya:
Brian
I'm not able to understand the tree notation you are using. Can you pictorially depict your tree? thanks for taking the trouble.

((a(bc))((de)((fg)h)))

A Bhattacharya
Ranch Hand
Posts: 125
Thanks for the picture. It is ok for 'a' to be at depth 2 and 'f' at depth 4. If you are comparing the heights of left and right subtrees of the root node, you should not even consider 'a' because it is not the deepest node in the left subtree.

Brian Cole
Author
Ranch Hand
Posts: 911
1
Originally posted by A Bhattacharya:
Thanks for the picture. It is ok for 'a' to be at depth 2 and 'f' at depth 4. If you are comparing the heights of left and right subtrees of the root node, you should not even consider 'a' because it is not the deepest node in the left subtree.

You're welcome.

That's why I said "depending on what exactly we mean by 'fully balanced.'"

In fact, some people define "fully balanced" to mean every leaf has exactly the same depth, which is pretty restrictive in that no binary tree with a leaf-count that is not a power of two can qualify. Note that the tree I demonstrated can be rebalanced to meet this definition: (((ab)(cd))((ef)(gh)))

If it were up to me, I'd say a "fully balanced" tree is one where the depths of any two leaves differ by at most one. I'd say the tree I demonstrated, where the depths of a and f differ by two, could possibly be considered "balanced" but not "fully balanced." But that's just me--feel free to use your own definition. (During a job interview, it might be wise to agree on a definition.)
[ May 08, 2008: Message edited by: Brian Cole ]