The complexity of the maxheight function in a binary tree

Question

Function:

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

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

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

So what is the difficulty?

Thanks.

Answer 1

On average for a balanced binary tree

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

Each recursive call gives you two half size problems. By the main theorem, this would estimate T (n) = Θ (n)

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

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

Which estimates T (n) = Θ (n)

Answer 2

The questions you should ask are:

• What represents N in my data structure (binary tree)
• How much must I go before I can determine the height of my structure.

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

For this reason, your algorithm is in O (N)