# Height of a red black tree

I'm almost done implementing a red black tree but I'm stuck with height. (Not black height). Can anyone give me a hint or the concept on how to implement height? I know the formula but its 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?

## Answers

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!