Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Diameter Of a Binary Tree

Objec­tive: - Given a binary tree, find the diam­e­ter of it.

What is Diam­e­ter Of a Tree: Diam­e­ter 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.

Exam­ple:

 

Diameter-Of-a-Binary-Tree

Diameter-Of-a-Binary-Tree

Approach:

Diam­e­ter of a tree w.r.t root can be defined as

Maximum(Diameter of left sub­tree, Diam­e­ter of right sub­tree, Longest path between two nodes which passes through the root.)

Now the diam­e­ter of left and right subtree’s can be solved recur­sively. And Longest path between two nodes which passes through the root can be cal­cu­lated as 1 + height of left sub­tree + 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 sub­tree, Diam­e­ter of right sub­tree, Longest path between two nodes which passes through the root.)

Time Com­plex­ity: Since when cal­cu­lat­ing the diam­e­ter, every iter­a­tion for every node, is cal­cu­lat­ing height of tree sep­a­rately in which we iter­ate the tree from top to bot­tom and when we cal­cu­late diam­e­ter recur­sively so its O(N2)

Code:

Output:
Diameter of Tree: 6

Now we will improve it fur­ther. If you notice at every node to find the diam­e­ter we are call­ing a sep­a­rate func­tion to find the height. We can improve it by find­ing the height of tree and diam­e­ter in the same iteration.

Approach:

Every node will return the two infor­ma­tion in the same iter­a­tion , height of that node and diam­e­ter of tree with respect to that node.

Code:

Output:
Diameter of Tree 6

You may also like...

  • Rishabh Gupta

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