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!


Need Your Help

finding the maximum number of 1's in a row

algorithm matrix binary-search

A 2d matrix is given filled with 1's and 0's. It is given that all 1's in a row come before all the 0's. We have to find the maximum number of 1's in a row.

Android : why does native_start fails in startNavigating() on Android 2.3.1 emulator?

java android android-emulator geolocation gps

I am using Android 2.3.1 project to get a current location using LocationManager.GPS_PROVIDER.