Michael Michael - 4 years ago 80
Java Question

Finding the height of the binary tree

Given the code for finding the height of a binary tree:

/*
class Node
int data;
Node left;
Node right;
*/
int height(Node root)
{
if(root == null){
return 0;
}
else{
int left = height(root.left);
int right = height(root.right);
if(left > right){
return 1 + left;
}
else{
return 1 + right;
}
}
}


The example is:

3
/ \
5 2
/ \ /
1 4 6
/
7


and the height is 4 because
3->2->6->7


I'm having big troubles with understanding the recursion process here. I'd appreciate anyone who explains me the following questions:

1) When traversing the tree, do the following two lines add 1 at each visit of the node? Bigger question: how does it work?

int left = height(root.left);
int right = height(root.right);


2) Do I understand it correctly?:
int left = height(root.left);
---> goes until the leftmost node ??
int right = height(root.right);
---> goes until the rightmost node ??

What happens if I had the following tree:

3
/ \
5 2
/ \ /
1 4 6
/ /
3 7
/
2


and the height would be 5 because of
3->5->4->3->2
?

I'm having difficulties with understanding the recursion of these lines:

int left = height(root.left);
int right = height(root.right);


My understanding about those lines is
left
goes to the leftmost node while
right
goes to the rightmost node.

Thanks in advance!

Answer Source

Basically you have a simple algorithm description and you implement it almost literally to obtain the recursive solution. You start from something like:

  • a tree with no nodes has height 0
  • a tree with any amount of nodes has height 1 + the maximum height between the left subtree and the right subtree

In a recursive algorithm you always have an recursive step (which is the second in this case) and a base case which stops the recursion (tree with no nodes).

So basically height of tree with root 3

     3
   /   \
  5     2
 / \    /
1   4  6
      /
     7

is 1 + maximum between the height of the two subtrees starting from 3, eg:

   5              2
  / \            /
 1   4          6
               /
              7  

So this is what is done by

int left = height(root.left);
int right = height(root.right);

Then recursively, height of

   5
  / \
 1   4

is maximum between height of subtrees

 1   4

and so on.

Basically at each recursive step you split the execution path into 2 to calculate the height of the subtrees, when both have been calculated you take the greater height, add 1 and return the value.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download