**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:**

** **

**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(N ^{2}) **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(N ^{2})**

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class DiameterOfTree { | |

public int getHeight(Node root) { | |

if (root != null) { | |

return 1 + Math.max(getHeight(root.left), getHeight(root.right)); | |

} | |

return 0; | |

} | |

public int Diameter(Node root) { | |

if (root != null) { | |

// get the left and right subtree height | |

int leftH = getHeight(root.left); | |

int rightH = getHeight(root.right); | |

// get the left diameter and right diameter recursively. | |

int leftDiameter = Diameter(root.left); | |

int rightDiameter = Diameter(root.right); | |

// get the max leftsubtree, rightsubtree, longest path goes through | |

// root. | |

return getMax(leftH + rightH + 1, leftDiameter, rightDiameter); | |

} | |

return 0; | |

} | |

public int getMax(int a, int b, int c) { | |

return Math.max(a, Math.max(b, c)); | |

} | |

public static void main(String[] args) { | |

Node root = new Node(1); | |

root.left = new Node(2); | |

root.right = new Node(3); | |

root.left.left = new Node(4); | |

root.left.right = new Node(5); | |

root.left.right.left = new Node(6); | |

root.left.right.left.right = new Node(7); | |

root.left.left.left = new Node(8); | |

DiameterOfTree d = new DiameterOfTree(); | |

System.out.println("Diameter of Tree: " + d.Diameter(root)); | |

} | |

} | |

class Node { | |

int data; | |

Node left; | |

Node right; | |

public Node(int data) { | |

this.data = data; | |

} | |

} |

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:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class DiameterOfTree { | |

int diameter = 0; | |

// here in improved solution, we calculate the height and diameter for every | |

// node in same iteration | |

// every Node will return 2 values, diameter and height wrt to the | |

// particular node | |

public int[] Diameter(Node root) { | |

int DandH[] = { 0, 0 }; // initialize the height (DandH[0]) and diameter | |

// as 0 (DandH[1]) | |

if (root != null) { | |

int[] leftResult = Diameter(root.left); | |

int[] rightResult = Diameter(root.right); | |

int height = Math.max(leftResult[0], rightResult[0]) + 1; | |

int leftDiameter = leftResult[1]; | |

int rightDiameter = rightResult[1]; | |

int rootDiameter = leftResult[0] + rightResult[0] + 1; | |

int finalDiameter = getMax(leftDiameter, rightDiameter, | |

rootDiameter); | |

// prepare the DandH[] | |

DandH[0] = height; // update the height | |

DandH[1] = finalDiameter; | |

return DandH; | |

} | |

return DandH; | |

} | |

public int getMax(int a, int b, int c) { | |

return Math.max(a, Math.max(b, c)); | |

} | |

public static void main(String[] args) { | |

Node root = new Node(1); | |

root.left = new Node(2); | |

root.right = new Node(3); | |

root.left.left = new Node(4); | |

root.left.right = new Node(5); | |

root.left.right.left = new Node(6); | |

root.left.right.left.right = new Node(7); | |

root.left.left.left = new Node(8); | |

DiameterOfTree d = new DiameterOfTree(); | |

System.out.println("Diameter of Tree: " + d.Diameter(root)[1]); | |

} | |

} | |

class Node { | |

int data; | |

Node left; | |

Node right; | |

public Node(int data) { | |

this.data = data; | |

} | |

} |

Output: Diameter of Tree 6