# Diameter of a Binary Tree

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) {
} else if (value > current.data) {
} else {
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);

}
}

``````

See more approaches.

Suggested post

Thank you for reaching out this tutorial. You can comment below in the comments section. See more Data Structure Problems.