The Diameter of a Binary Tree or Width of a Binary Tree is the number of nodes on the longest path between two end nodes.
The diagram below shows the diameter 9 of the tree the leaves that forms ends of the longest path are in shaded (The longest path is 9).
Explanation:
1. The diameter of left subtree.
2. Diameter of right subtree.
3. Compare both the path.
Below is the Recursive implementation of the approach
public class BinaryTreeBT {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// creating binary tree
static class BinaryTree {
static int id = -1;
public static Node createBinary(int nodes[]) {
id++;
if (nodes[id] == -1) {
return null;
}
Node myNode = new Node(nodes[id]);
myNode.left = createBinary(nodes);
myNode.right = createBinary(nodes);
return myNode;
}
/* function to insert element in binary tree */
public static Node add(Node current, int value) {
if(current == null){
return new Node(value);
}
if (value < current.data) {
current.left = add(current.left, value);
} else if (value > current.data) {
current.right = add(current.right, value);
} else {
// value already exists
return current;
}
return current;
}
}
// getting diameter of tree
public static class TreeDiam {
int ht, diam;
TreeDiam(int ht, int diam) {
this.ht = ht;
this.diam = diam;
}
}
public static TreeDiam getDiameter(Node root) {
if (root == null) {
return new TreeDiam(0, 0);
}
TreeDiam left = getDiameter(root.left);
TreeDiam right = getDiameter(root.right);
int myHeight = Math.max(left.ht, right.ht) + 1;
int dim1 = left.diam;
int dim2 = right.diam;
int dim3 = left.ht + right.ht + 1;
int myDiameter = Math.max(Math.max(dim1, dim2), dim3);
TreeDiam treeInfo = new TreeDiam(myHeight, myDiameter);
return treeInfo;
}
public static void main(String[] args) {
int nodeArr[] = { 1, 2, 4, -1, -1, 5, -1, -1, 3, -1, 6, -1, -1 };
BinaryTree tree = new BinaryTree();
Node result = tree.createBinary(nodeArr);
System.out.print(getDiameter(result).diam);
}
}
Answer: 5
See more approaches.
Suggested post
Can you Find Height of The Binary Tree?
Thank you for reaching out this tutorial. You can comment below in the comments section. See more Data Structure Problems.
