# How to calculate the height of a red black tree?

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 n2.

## 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!