Balance factor of nodes in AVL Tree???

Question

to calculate balance factor of a node in 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 to calculate the the height of left subtree or right subtree for example in the given figer the height of left subtree of root node 40 is 4 and the height of right subtree of 40 is 2 so the difference of heights is 2, but how i will do this in c++ code. i don't want to use recurrsion because it is very confusing task using explicit stack instead of recurssion is much more understandable.

Answer 1

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;
}