1

I have seen various posts here that computes the diameter of a binary tree. One such solution can be found here (Look at the accepted solution, NOT the code highlighted in the problem).

I'm confused why the time complexity of the code would be O(n^2). I don't see how traversing the nodes of a tree twice (once for the height (via getHeight()) and once for the diameter (via getDiameter()) would be n^2 instead of n+n which is 2n. Any help would be appreciated.

Community
  • 1
  • 1
Bugaboo
  • 973
  • 1
  • 17
  • 36

3 Answers3

2

As you mentioned, the time complexity of getHeight() is O(n). For each node, the function getHeight() is called. So the complexity for a single node is O(n). Hence the complexity for the entire algorithm (for all nodes) is O(n*n).

Dinesh
  • 2,194
  • 3
  • 30
  • 52
2

It should be O(N) to calculate the height of every subtree rooted at every node, you only have to traverse the tree one time using an in-order traversal.

int treeHeight(root)
{
   if(root == null) return -1;

   root->height = max(treeHeight(root->rChild),treeHeight(root->lChild)) + 1;
   return root->height;
}

This will visit each node 1 time, so has order O(N).

Combine this with the result from the linked source, and you will be able to determine which 2 nodes have the longest path between in at worst another traversal.

Indeed this describes the way to do it in O(N)

The different between this solution (the optimized one) and the referenced one is that the referenced solution re-computes tree height every time after shrinking the search size by only 1 node (the root node). Thus from above the complexity will be O(N + (N - 1) + ... + 1).

The sum 

1 + 2 + ... + N

is equal to 

= N(N + 1)/2

And so the complexity of sum of all the operations from the repeated calls to getHeight will be O(N^2)

For completeness sake, conversely, the optimized solution getHeight() will have complexity O(1) after the pre computation because each node will store the value as a data member of the node.

waTeim
  • 9,095
  • 2
  • 37
  • 40
  • I'm not looking for an optimized solution which works in O(n). I want to know why the solution I mentioned in my question has the time complexity of O(n^2)? – Bugaboo Jan 26 '14 at 04:54
0

All subtree heights may be precalculated (using O(n) time), so what total time complexity of finding the diameter would be O(n).

Egor Skriptunoff
  • 23,359
  • 2
  • 34
  • 64
  • I'm not looking for an optimized solution which works in O(n). I want to know why the solution I mentioned in my question has the time complexity of O(n^2)? – Bugaboo Jan 26 '14 at 04:55