Wednesday, August 10, 2011

Diameter of a binary tree

Problem:
Find the diameter of a binary tree.
Solution:

  1. Do Post order traversal
  2. if Left Max path + Right Max path > Max then
  3. Max = Left Max path + Right Max path 
  4. return 1 + MAX(Left Max path length + Right Max path length)

Complexity: O(n), where n = no of nodes
Code:

No comments:

Post a Comment