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 ]