c++ - Red-Black Tree Height using Recursion

Question

I have these following methods to get the height of a red black tree and this works (I send the root). Now my question is, how is this working? I have drawn a tree and have tried following this step by step for each recursion call but I can't pull it off. I know the general idea of what the code is doing, which is going through all the leaves and comparing them but can anyone give a clear explanation on this?

int RedBlackTree::heightHelper(Node * n) const{
        if ( n == NULL ){
            return -1;
        }
        else{
            return max(heightHelper(n->left), heightHelper(n->right)) + 1;
        }
    }

int RedBlackTree::max(int x, int y) const{
    if (x >= y){
        return x;
    }
    else{
        return y;
    }
}

Answer 1

Well, the general algorithm to find the height of any binary tree (whether a BST,AVL tree, Red Black,etc) is as follows

For the current node:
 if(node is NULL) return -1
 else
    h1=Height of your left child//A Recursive call
    h2=Height of your right child//A Recursive call
    Add 1 to max(h1,h2) to account for the current node
    return this value to parent.

An illustration to the above algorithm is as follows:

(Image courtesy Wikipedia.org)