Java Program to Find the Diameter of a Binary Tree

This Java program calculates the diameter of a binary tree. The diameter is defined as the number of nodes on the longest path between two leaves in the tree. This measure can be crucial for understanding the tree’s structure and for operations that require processing longest paths, like network routing and tree balancing.

Binary Tree Class

The BinaryTree class includes a Node inner class, a method to find the diameter, and a helper method to calculate the height of the tree.

public class BinaryTree {
    static class Node {
        int data;
        Node left, right;

        public Node(int item) {
            data = item;
            left = right = null;
        }
    }

    Node root;
    int maxDiameter = 0; // This will hold the maximum diameter

    // Function to calculate diameter of the binary tree
    public int diameter() {
        calculateHeight(root);
        return maxDiameter;
    }

    // A utility function to calculate height of the tree and update diameter
    private int calculateHeight(Node node) {
        if (node == null)
            return 0; // Base case where the height of an empty subtree is 0

        // Calculate height of each subtree
        int leftHeight = calculateHeight(node.left);
        int rightHeight = calculateHeight(node.right);

        // Update the diameter if the path through the root is larger
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight + 1);

        // Return height of tree rooted at this node
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);

        System.out.println("The diameter of the tree is: " + tree.diameter());
    }
}

Explanation of the Methods

• diameter – Public method to start the process of finding the tree’s diameter. It calls a private method to calculate the height and simultaneously updates the diameter.
• calculateHeight – Private recursive method that calculates the height of the tree from the node, updating the diameter based on the path that passes through each node.

Conclusion

The provided Java implementation effectively finds the diameter of a binary tree, integrating the calculation with height measurements to optimize performance. This functionality is important for applications that need to manage or optimize tree structures efficiently.