height of a tree

recursive or non recursive

Page 1 of 1

2 Replies - 20859 Views - Last Post: 22 February 2010 - 10:49 PM Rate Topic: -----

#1 amitx  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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.....
so please help me out
Is This A Good Question/Topic? 0
  • +

#10 Voodoo Doll  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • 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.
Was This Post Helpful? 1

#11 Guest_travis*


Reputation:

Re: height of a tree

Posted 22 February 2010 - 10:49 PM

thanks
Was This Post Helpful? 0

Page 1 of 1