Diameter of a tree

Problem Statement

Given a binary tree, find the diameter (width) of the tree. The diameter is the length of the longest path between any two nodes. This path may or may not pass through the root.

Example:

• Input: Root of the above tree
• Output: 3 (path: 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3)

Approach 1: Brute Force (Calculate Height at Each Node)

Intuition

At each node, the diameter passing through it is the sum of heights of left and right subtrees. Calculate this for every node and track the maximum.

Algorithm

1. For each node, calculate left height and right height
2. Diameter at that node = leftHeight + rightHeight
3. Recursively check all nodes and return maximum diameter

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int height(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(height(root.left), height(root.right));
    }
    
    public int diameterBruteForce(TreeNode root) {
        if (root == null) return 0;
        
        // Diameter passing through this node
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        int diameterThroughRoot = leftHeight + rightHeight;
        
        // Diameter in left or right subtree
        int leftDiameter = diameterBruteForce(root.left);
        int rightDiameter = diameterBruteForce(root.right);
        
        return Math.max(diameterThroughRoot, 
                       Math.max(leftDiameter, rightDiameter));
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - For each node, we calculate height which takes O(n)
• Space Complexity: O(n) - Recursion stack for skewed tree

Approach 2: Optimal (Single Pass - Compute Height and Diameter Together)

Intuition

Instead of calculating height separately for each node, compute height while simultaneously tracking the maximum diameter. This way, each node is visited only once.

Algorithm

1. Create a helper function that returns height but also updates max diameter
2. At each node: diameter = leftHeight + rightHeight
3. Update global maximum diameter
4. Return height for parent's calculation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int maxDiameter = 0;
    
    private int height(TreeNode root) {
        if (root == null) return 0;
        
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        
        // Update diameter at this node
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
        
        return 1 + Math.max(leftHeight, rightHeight);
    }
    
    public int diameter(TreeNode root) {
        maxDiameter = 0;
        height(root);
        return maxDiameter;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Each node is visited exactly once
• Space Complexity: O(h) - Recursion stack depth, where h is height of tree

Key Takeaways

1. Diameter formula: leftHeight + rightHeight at each node
2. The optimal approach combines height calculation with diameter tracking
3. The longest path may not pass through the root
4. This pattern of "compute while returning" is common in tree problems
5. Similar approach can be used for finding the longest path in any tree structure