Binary Tree’s Diameter: Easy Explanation to Find its value

Introduction

The longest path length between any two nodes of a binary tree is called its diameter (Binary Tree’s Diameter). This path may or may not cross the root. Importantly, the length is measured by the number of edges between the nodes on this path, not the number of nodes.

To solve this problem efficiently, a recursive approach is often used, where we simultaneously compute the height of each subtree and keep track of the longest path encountered so far.

Approach to the Problem of the Binary Tree’s Diameter

To calculate the diameter, we need to determine the longest path between two nodes. For any given node, the longest path that passes through it is the sum of the heights of its left and right subtrees. As we calculate the height recursively, we can update the maximum diameter whenever a longer path is found.

This involves:

• A recursive function to calculate the height of a node
• Keeping a reference to the maximum diameter found so far
• Updating this maximum during each recursive call based on the left and right subtree heights

Java Implementation

Here’s an implementation in Java to find the diameter of a binary tree:

public class BinaryTreeDiameter {
    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        computeHeight(root);
        return diameter;
    }

    private int computeHeight(TreeNode node) {
        if (node == null) return 0;

        int leftHeight = computeHeight(node.leftNode);
        int rightHeight = computeHeight(node.rightNode);

        diameter = Math.max(diameter, leftHeight + rightHeight);

        return Math.max(leftHeight, rightHeight) + 1;
    }

    public static void main(String[] args) {
        /*
            Example Tree:
                  1
                 / \
                2   3
               / \     
              4   5    

            Expected diameter: 3 (path: 4 -> 2 -> 1 -> 3)
        */
    	BinaryTreeDiameter binaryTreeDiameter = new BinaryTreeDiameter();
        TreeNode root = binaryTreeDiameter.new TreeNode(1);
        root.leftNode = binaryTreeDiameter.new TreeNode(2);
        root.rightNode = binaryTreeDiameter.new TreeNode(3);
        root.leftNode.leftNode = binaryTreeDiameter.new TreeNode(4);
        root.leftNode.rightNode = binaryTreeDiameter.new TreeNode(5);

        BinaryTreeDiameter tree = new BinaryTreeDiameter();
        int result = tree.diameterOfBinaryTree(root);
        System.out.println("Diameter of the tree is: " + result);
    }
    
    class TreeNode {
        int nodeVal;
        TreeNode leftNode;
        TreeNode rightNode;

        TreeNode(int nodeVal) {
            this.nodeVal = nodeVal;
        }
    }
}

Time and Space Complexity for Binary Tree’s Diameter

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to recursive call stack.

Conclusion

This approach offers a concise and efficient way to compute the diameter of a binary tree. By calculating the height and updating the diameter in the same traversal, we avoid redundant computations and achieve optimal performance.

You can find the example code on Github.