 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. Anonymous

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