[amitx]

how to find the height of a tree using recursive or non recursive algo
this question was asked in an interview with some mnc.....
so please help me out

[Voodoo Doll]

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.