Balance factor of nodes in AVL Tree

Question

To calculate the balance factor of a node in an AVL tree we need to find the height of its left subtree and the height of its right subtree. Then we subtract the height of right subtree from the height of its left subtree:

balancefactor = leftsubtreeheigh - rightsubtreeheight

My question is: How do I calculate the height of the left subtree or the right subtree?

For example in the given figure^₁ the height of the left subtree of the root node 40 is 4 and the height of the right subtree of 40 is 2 so the difference of the heights is 2.

How do I do this in C++? I don't want to use recursion because it's very confusing. Using an explicit stack instead of recursion is much more understandable.

^₁ The figure has been deleted from the imgur servers.

Dupe of stackoverflow.com/questions/1979335/… asked yesterday by same user. — anon

R Samuel Klatchko R Samuel Klatchko · Accepted Answer · 2009-12-31T19:40:13

The depth of a node is 1 more then the depth of it's deepest child.

You can do this quite simply with recursion.

unsigned int depth(node *n)
{
    if (n == NULL)
        return 0;
    else
        return MAX(depth(n->left), depth(n->right)) + 1;
}

Balance factor of nodes in AVL Tree

2 Answers