# height of a tree

Page 1 of 1

## 2 Replies - 28836 Views - Last Post: 22 February 2010 - 10:49 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=14533&amp;s=a973be56af40f988fd5fe62c726650dd&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 amitx

Reputation: 0
• Posts: 10
• Joined: 02-February 06

# height of a tree

Posted 02 February 2006 - 11:49 PM

how to find the height of a tree using recursive or non recursive algo
this question was asked in an interview with some mnc.....
Is This A Good Question/Topic? 0

### #10 Voodoo Doll

Reputation: 12
• Posts: 108
• Joined: 24-January 06

## Re: height of a tree

Posted 03 February 2006 - 08:25 AM

Do a post order traversal on the tree, I'll assume you know how that works. If you get to a leaf, return -1, then for every other node, return the larger of the left and right subtrees plus 1.
```height(tree)
if tree != leaf
l = height(tree.left)
r = height(tree.right)

if l > r
ret l + 1
else
ret r + 1
else
ret -1

```

Let's say you have this tree.
```        A

B       C

D   E   F

G

```

D, E, and G will return 0 because both l and r will be -1, and -1 + 1 is 0. Then F and B will return 1, C will return 2, and A will return 3. Depending on your definition of tree height, that's the correct height of the tree. And you only had to visit every node to find it. The alternative definition has the height at 4, and you can return 0 at a leaf to get it.

Reputation:

## Re: height of a tree

Posted 22 February 2010 - 10:49 PM

thanks