How to calculate the height of a red black tree?

Question

I'm almost done implementing a red black tree, but I'm stuck with how to calculate the height (not black height). Can anyone give me a hint or the concept on how to implement the height? I know the formula, but it's not much of a help.

I thought of traversing each node and adding a counter, but this gets complicated as the red black tree gets bigger.

Basically how do I know when it has travelled down to its longest path?

I'm not really concerned with the time complexity of the solution, but I would like to avoid n².

Answer 1

There is a simple recursive approach for computing the height of a tree that works in time O(n), where n is the number of nodes. The idea is to compute the heights of each node's children, then to take the maximum of those values, plus one. Here's some pseudocode:

function treeHeight(node n) {
    if (n is null) return -1;
    return max(treeHeight(n.left), treeHeight(n.right)) + 1;
}

This visits every node exactly once and does O(1) work per node, so the total time complexity is O(n).

Hope this helps!