c++data-structuresbinary-treeavl-treetree-balancing

Calculating AVL tree node balance from it's children nodes' balances

Say I have an AVL tree such that it's nodes store their own balance factor as a single integer.

How can I calculate the balance factor of a node N if I know the balance factor of both it's left and right child.

Note that I DO NOT have the rHeight and lHeight, so bal(N) = lHeight - rHeight is not an option.

Solution

  • Short answer - you can't.

    Long answer:

    Consider these two trees:

               A
        /     \
     B           C                   A
   /   \       /   \                / \
  D     E     F     G              B   C
 / \   / \   / \   / \
H   I J   K L   M N   O

    They have the same balance factor, but they aren't the same height.

    So, if you only have the balance factor of the child, you don't know how high that subtree is, thus you can't use only that to calculate the balance factor of the parent.