Problem Statement

Given the root of a binary tree, you need to compute the diameter of the tree.

Diameter is defined as the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

• Length of a path is measured in number of edges.

Example:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: Longest path is [4,2,1,3] or [5,2,1,3] with 3 edges.

Approach

1. The diameter at a node is the sum of left subtree height + right subtree height.
2. We can recursively compute the height of each subtree while keeping track of the maximum diameter found so far.
3. Use a helper function that returns the height of a subtree and updates the maximum diameter.

Java Implementation

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) { 
        this.val = val; 
    }
}

class Solution {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return maxDiameter;
    }

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

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

        // Update diameter at this node
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

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

Explanation

1. Base Case:
   • If the node is null, height is 0.
2. Recursive Case:
   • Compute leftHeight and rightHeight for left and right subtrees.
3. Update Maximum Diameter:
   • The diameter at this node is leftHeight + rightHeight.
   • Update maxDiameter if this value is greater.
4. Return Height:
   • Height of a node = 1 + max(leftHeight, rightHeight).

Example Walkthrough

Consider this tree:

        1
       / \
      2   3
     / \
    4   5

1. Height of node 4 = 1, node 5 = 1 → node 2: height = 1 + max(1,1) = 2.
2. Diameter at node 2 = 1 + 1 = 2 → maxDiameter = 2.
3. Height of node 3 = 1 → diameter at root = 2 + 1 = 3 → maxDiameter = 3.

Result = 3 edges.

Time Complexity: O(n) – Each node is visited once.
Space Complexity: O(h) – Recursion stack, where h is the tree height.