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

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!

### finding the maximum number of 1's in a row

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?

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