Find Binary Tree Height with O(n/2)

[Chris Shoban]

Given a binary tree (balanced or in-balanced), write the code to find the tree's height in O(n/2).

So I was given this for an interview question the other day. I was told that O(n) is the easy answer, but they wanted to see how I would improve the algorithm. It is stuck in my head as I could only discuss the O(n) solution, starting from the root and recursively checking the left and right child node while increasing the count. Yet since this would traverse every node, the run time is O(n). The other possible solution that I offered, which do not suffice, is to somehow know whether the left or right sub-tree is somehow longer and traverse only that sub-tree, therefore only checking half the nodes. Another option I tried to argue, is if the system runs on a dual-core (or multiple core), one core could be used for the left sub-tree and find it's height and another core would be used for the right sub-tree and the time is cut in half since each core works on half a binary tree.

Another confusion for me, is I thought O(n) == O(n/2) as 1/2 is the leading constant which would be disregarded.

Is it possible to find the height with a speed faster than O(n)?

Any thoughts?

[Paul Clapham]

Chris Shoban wrote:Another confusion for me, is I thought O(n) == O(n/2) as 1/2 is the leading constant which would be disregarded.

Yes, that's exactly correct. Perhaps they meant something else?

[Mike Peters]

For a balanced tree the depth of the tree is log2(N) you don't need an algorithm for that. For an non-balanced tree the depth is between log2(N) and N. You can only calculate this with an O(N) algorithm if your data structure does not contain any additional depth information.

[kri shan]

For a balanced tree the depth of the tree is log2(N) you don't need an algorithm for that. For an non-balanced tree the depth is between log2(N) and N. You can only calculate this with an O(N) algorithm if your data structure does not contain any additional depth information.

How to find the depth of a non balanced binary tree's from root node ? (Which algorithm gives best performance)