- Given a binary tree, find out the diameter using recursive algorithm.
- Traverse the binary tree using depth first search (DFS) algorithm.
- What is diameter of binary tree?
- Diameter is the longest distance between two leaf nodes in a binary tree.
Examples – find diameter of binary tree (recursive)
Example 1: calculate diameter of binary tree
Longest path between leaf nodes is:
- Node K -> Node H -> Node K or Node L -> Node H -> Node K
- It need 3 hops to travel between the nodes, So, the diameter is 3.
Example 2: find diameter of binary tree (DFS)
Let us find some of path between leaf nodes.
| S. No. | Leaf nodes | Probable path | Hops |
|---|---|---|---|
| 1 | K,L | K-> H -> L | 3 |
| 2 | K,I | K -> H -> D->I | 4 |
| 3 | L,I | L -> H -> D->I | 4 |
Clearly path 2 and 3 gives the longest path i.e. 4. So Diameter = 4.
Example 3: Calculate diameter at each non leaf of binary tree
Let us calculate the diameter at each non leaf node and one of the probable path (multiple paths may exist for same diameter).
| S. No. | Non-Leaf-Node | Probable path | Diameter |
|---|---|---|---|
| 1 | H | K -> H -> L | 3 |
| 2 | J | M-> J-> N | 3 |
| 3 | D | K-> H -> D -> I | 4 |
| 4 | E | E-> J-> M | 3 |
| 5 | B | K-> H -> D -> E-> J-> M | 7 |
Example 3 is our base to calculate the the diameter in binary tree i.e. we will be calculating the diameter at each node. The longest path between leaf nodes is through Node B. (refer above table).
Brief algorithm to calculate diameter of binary tree
- Calculate the diameter at each non leaf node in a binary tree.
- Pass max depth height of left subtree or right subtree to its parent node.
- e.g Diameter at Node H is 3.
- Maximum height at Node H is 2
- Node H will return 2 to its parent node i.e. Node D.
- By applying above algorithm, we can calculate the diameter of binary tree.
- Maximum diameter is of binary tree is 7 (refer Fig 5).
Program – Calculate diameter of binary tree (recursive algorithm)
1.) DiameterOfBTree Class: DiameterOfBTree class is used to find diameter of a binary tree.
package org.learn.Question;
public class DiameterOfBTree {
int diameter = 0;
private int diameterOfBTree(Node root) {
if (null == root)
return 0;
int left = diameterOfBTree(root.left);
int right = diameterOfBTree(root.right);
diameter = Math.max(diameter, left + right + 1);
return Math.max(left, right) + 1;
}
public int getDiameter(Node root) {
diameterOfBTree(root);
int diameterTree = diameter;
//reset diameter
diameter = 0;
return diameterTree;
}
}
2.) Node Class: Node class representing nodes of a binary tree.
package org.learn.Question;
public class Node {
public int data;
public Node left;
public Node right;
public Node(int num) {
this.data = num;
this.left = null;
this.right = null;
}
public Node() {
this.left = null;
this.right = null;
}
public static Node createNode(int number) {
return new Node(number);
}
}
3.) App Class:
- We are constructing binary tree in a main method.
- We are calling method of DiameterOfBTree class calculate diameter of a binary tree.
package org.learn.Client;
import org.learn.Question.DiameterOfBTree;
import org.learn.Question.Node;
public class App {
public static void main(String[] args) {
// Level 0
Node A = Node.createNode(70);
// Level 1
Node B = Node.createNode(40);
Node C = Node.createNode(80);
// Level 2
Node D = Node.createNode(70);
Node E = Node.createNode(40);
Node F = Node.createNode(80);
Node G = Node.createNode(80);
// Level 3
Node H = Node.createNode(70);
Node I = Node.createNode(40);
Node J = Node.createNode(80);
// Level 4
Node K = Node.createNode(70);
Node L = Node.createNode(40);
Node M = Node.createNode(80);
Node N = Node.createNode(80);
// Connect level 0 to level 1
A.left = B;
A.right = C;
// Connect level 1 to level 2
B.left = D;
B.right = E;
C.left = F;
C.right = G;
// Connect level 2 to level 3
D.left = H;
D.right = I;
E.right = J;
// Connect level 2 to level 3
H.left = K;
H.right = L;
J.left = M;
J.right = N;
DiameterOfBTree objDiameter = new DiameterOfBTree();
System.out.println("1. Diameter at Node K is : " + objDiameter.getDiameter(K));
System.out.println("2. Diameter at Node H is : " + objDiameter.getDiameter(H));
System.out.println("3. Diameter at Node D is : " + objDiameter.getDiameter(D));
System.out.println("4. Diameter at Node B is : " + objDiameter.getDiameter(B));
System.out.println("5. Diameter of Binary Tree is : " + objDiameter.getDiameter(A));
}
}
Output – diameter of binary tree at different nodes
1. Diameter at Node K is : 1 2. Diameter at Node H is : 3 3. Diameter at Node D is : 4 4. Diameter at Node B is : 7 5. Diameter of Binary Tree is : 7
Download Example – Diameter binary tree (recursive)
