# 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

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 🙁