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.

Answer 1

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.

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)