Complexity for the function maxheight in a binary tree

Question

The function:

MAX-HEIGHT(node) 
  if(node == NIL) 
      return -1;
  else 
     return max(MAX-HEIGHT(node.leftChild), MAX-HEIGHT(node.rightChild)) + 1;

Suppose that we have N nodes and we call the function with MAX-HEIGHT(root).

I think that the complexity of this function is O(N) because we need to visit each node. However, I am not sure and I can not prove it rigorously. Please give me a good explanation why it is O(N), if it is O(N), and why not if it is not O(N).

So, what is the complexity?

Thank you.

Crossroads

BTW, you can customize the tree to keep the information internally, and make it a O(1) operation, and recompute it upon tree modification (for a balanced tree, re-computation-after-modification will be a O(log n) operation) – Rhpositive

Answer 1

In the average case, for a balanced binary tree

T(n) = 2T(n/2) + Θ(1);

Every recursive call gives you two problems of half the size. By master theorem, this would evaluate to T(n) = Θ(n)

In the worst case, where each node has only one child.

T(n) = T(n-1) + Θ(1)

Which evaluates to T(n) = Θ(n)

Byroad

it's not the most formal answer, but must be proof enough. – Byroad

It is a good answer since you are using the master theorem (without showing the steps) to prove it. – Fenn

Answer 2

The questions you should ask are:

• What does N represent in my data structure (a binary tree)
• How many N do I have to go through before I can determine the height of my structure.

Here, N represent the number of nodes in your tree, and you have to go through all of them before returning the height.

For that reason your algorithm is in O(N)

Minnieminnnie

Answer 3

Here is another approach for this. I could be wrong in some of these calculations, so please correct me.

We can write

T(n) = 2 T(n/2) + c for all n > 1, where c is some constant. And 
T(n) = 1 when n = 1

So T(n) = 2 T(n/2) + c, now start substituting T(n/2) and move one

=> T(n) = 2 [ 2 T(n/4) + c ] + c
=> T(n) = 2^2T(n/4) + 2c

Now substitute t(n/4) as well
=> T(n) = 2^2[2 T(n/8) + c] + 2c
=> T(n) = 2^3T(n/8) + 3c

Now assume that if we keep dividing like this, at some point we will reach 1 i.e., when n/2^k = 1, then T(1) = 1

=> T(n) = 2^kT(n/2^k) + kc

Now since we know that n/2^k = 1
=> k = log n (I am representing log as base 2)

Therefore substitute k value in above T(n) equation to get
=> T(n) = 2^(log n) T(1) + c log n
=> T(n) = n T(1) + c log n (Check log rule on how we got n for first coefficient)
=> T(n) = n + c log n (since T(1) = 1)

Therefore T(n) = O(n) since n dominates log n in growth rate.

Pintsize