Diameter Of a Binary Tree

Objective: – Given a binary tree, write an algorithm to find the diameter of the tree.

What is Diameter Of a Tree: Diameter of tree is defined as A longest path or route between any two nodes in a tree. The path may or may not for through the root.

Example:

 

Diameter Of a Binary Tree

Approach:

Diameter of a tree w.r.t root can be defined as

Maximum(Diameter of left subtree, Diameter of right subtree, Longest path between two nodes which passes through the root.)

Now the diameter of left and right subtree’s can be solved recursively. And Longest path between two nodes which passes through the root can be calculated as 1 + height of left subtree + height of right subtree.

Please read this post to know how to find the Height of a tree.

We will explain Two approaches , First one will be Naive approach -O(N2) and then we will improve it to O(N).

Naive Approach:

  • Find the height of left subtree.
  • Find the height of right subtree.
  • Find the left diameter.
  • Find the right diameter.
  • Return the Maximum(Diameter of left subtree, Diameter of right subtree, Longest path between two nodes which passes through the root.)

Time Complexity: Since when calculating the diameter, every iteration for every node, is calculating height of tree separately in which we iterate the tree from top to bottom and when we calculate diameter recursively so its O(N2)

Code:

Output:
Diameter of Tree: 6

Now we will improve it further. If you notice at every node to find the diameter we are calling a separate function to find the height. We can improve it by finding the height of tree and diameter in the same iteration.

Approach:

Every node will return the two information in the same iteration , height of that node and diameter of tree with respect to that node.

Code:


Output:
Diameter of Tree 6

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • Rishabh Gupta

    Diameter of node, why is it leftH + rightH + 1?
    I think it should be leftH + rightH + 2. Help me, I am confused 🙁

    • Sanjeet Kumar

      Here we add 1,because it represents longest path through root node but in program we first calculate left height(i.e, left path “excluding root node” to leaf node) and then right height(i.e, right path “excluding root node” to leaf node) and then to get the total path length we add 1 for root node. i hope you got it.

%d bloggers like this: