How do I determine the height of nodes in a AVL tree?

**ryuzog** · 11-09-2010, 01:21 AM

I need to compare the heights of the nodes to the left and right of my current node.

But since the higher height overrides lower heights, I'd need to create a separate count for each "fork in the road" and then compare them all..

This seem laborious for something like starting from the root.

Either that or each node has a native height variable...which should be increased whenever it has a child...or its child has a child...but if two children of the same height have a child and ones child has a child, but the other doesn't, then node should take into account only the one with the child...

How can height be calculate without all this confusion...

**JosAH** · 11-09-2010, 08:08 AM

Originally Posted by ryuzog

I need to compare the heights of the nodes to the left and right of my current node.

But since the higher height overrides lower heights, I'd need to create a separate count for each "fork in the road" and then compare them all..

This seem laborious for something like starting from the root.

Either that or each node has a native height variable...which should be increased whenever it has a child...or its child has a child...but if two children of the same height have a child and ones child has a child, but the other doesn't, then node should take into account only the one with the child...

How can height be calculate without all this confusion...

I think you have it all upside down: the height of the root is 0 and the height of its children (if any) are 1 etc. etc. Do you really want to know the height of every node? In an AVL tree it is sufficient (and necessary) to know whether or not a (sub)tree is balanced; the numbers -1, 0 and 1 would be enough for each node. If you really want to know the height of each node the following recursive method sets the height of each node:

Java Code:

public void setHeight(Node root, int height) {
   if (root != null) {
      root.height= height;
      setHeight(root.left, height+1);
      setHeight(root.right, height+1);
   }
}

kind regards,

Jos

**ryuzog** · 11-09-2010, 01:34 PM

But wouldn't I need to know the height/(or depth?) to determine whether a node is balanced or not? Now that I think about it "height" isn't used, it's some...other thing similar to height. You have to count up from the bottommost node(s) and take the max...determine whether the difference is greater than one...I have the logic of the tri-node restructure down, I just don't know an easy way to determine whether or not a node is unbalanced or not.

p.s. that is some wonderful code though =) , an elegant way to deal with splits.