Michael - 4 years ago 80

Java Question

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

`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:

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

int right = height(root.right);

2) Do I understand it correctly?:

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

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

What happens if I had the following tree:

`3`

/ \

5 2

/ \ /

1 4 6

/ /

3 7

/

2

and the height would be

`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`

`right`

Thanks in advance!

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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**