Diameter of Binary Tree - Java Solution

1. Introduction

This blog post explores a common problem in binary tree algorithms: finding the diameter of a binary tree. The diameter is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root, and the length is measured in terms of the number of edges.

Problem

Given the root of a binary tree, the task is to return the length of the diameter of the tree. This involves finding the longest path between any two nodes within the tree.

2. Solution Steps

1. Use a recursive approach to traverse the tree.

2. For each node, calculate the height of its left and right subtrees.

3. The diameter at each node is the sum of the heights of its left and right subtrees.

4. Update the maximum diameter found during the traversal.

5. Return the maximum diameter after traversing the entire tree.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class DiameterOfBinaryTree {
    private static int maxDiameter;

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

        System.out.println(diameterOfBinaryTree(root)); // Test the function
    }

    // Function to calculate the diameter of a binary tree
    public static int diameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        height(root);
        return maxDiameter;
    }

    // Helper function to calculate the height of the tree
    private static int height(TreeNode node) {
        if (node == null) return 0;

        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        // Update the maximum diameter
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

        // Return the height of the tree
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Output:

3

Explanation:

1. diameterOfBinaryTree: This function initializes maxDiameter to zero and calls the height function to compute the height of the tree, updating the diameter along the way.

2. height: A helper function that recursively calculates the height of the tree. At each node, it computes the height of the left and right subtrees and updates the maxDiameter based on the sum of these heights.

3. The function returns the height of the current node, while the diameter is calculated as the sum of the heights of the left and right subtrees.

4. The maximum diameter is maintained and updated throughout the traversal, and the final value represents the diameter of the tree.

5. This method efficiently computes the diameter by considering the maximum span at each node, which includes the longest paths in its left and right subtrees.