*
The moose likes Java in General and the fly likes How will you find if a binary tree is fully balanced? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "How will you find if a binary tree is fully balanced?" Watch "How will you find if a binary tree is fully balanced?" New topic
Author

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

A Bhattacharya
Ranch Hand

Joined: Oct 22, 2007
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

Joined: Oct 13, 2005
Posts: 37907
    
  22
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

Joined: Oct 27, 2005
Posts: 19649
    
  18

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.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Brian Cole
Author
Ranch Hand

Joined: Sep 20, 2005
Posts: 862
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 ]

bitguru blog
A Bhattacharya
Ranch Hand

Joined: Oct 22, 2007
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

Joined: Sep 20, 2005
Posts: 862
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

Joined: Oct 22, 2007
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

Joined: Sep 20, 2005
Posts: 862
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 ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: How will you find if a binary tree is fully balanced?
 
Similar Threads
BST problem (Online waiting)
Find Binary Tree Height with O(n/2)
Recent interview question - Find a pair in array whose sum is x.
need help with binary search tree
Binary Tree remove node algorithms