L16. Diameter of Binary Tree | C++ | Java

Understanding how to calculate the Diameter of a Binary Tree is a quintessential Data Structures and Algorithms (DSA) problem. It bridges basic tree traversals with optimized state-sharing techniques, allowing us to compute structural properties efficiently in linear time.

1. Why Do We Need This? (Problem Statement & Status Quo)

When navigating hierarchical data structures like binary trees, measuring the span or reach between nodes is a frequent requirement in networking, file systems, and decision-tree architectures.

• The Definition of Diameter: The diameter of a binary tree is defined as the length of the longest path between any two nodes in that tree.
• Crucial Caveat: This path does not necessarily need to pass through the root node. It can span entirely within a left subtree, entirely within a right subtree, or bridge across the root from a node on the left to a node on the right.

2. Core Mental Model & Path Anatomy

To visualize how paths are formed in a binary tree, consider the following structural examples:

Tree 2 (Path does NOT pass through root):
            1
           / 
          2   
         /     
        3       
       / \
      6   ... (Longest path is local to a subtree)

For any given node in a binary tree, the longest path that passes through that specific node is equal to:

Thus, the global diameter of the binary tree is simply the maximum of $(\text{Left Height} + \text{Right Height})$ across all nodes in the tree.

3. Naive Approach vs. The Performance Bottleneck ($O(N^2)$)

The Brute-Force Strategy

A straightforward, intuitive way to solve this is to visit every single node in the tree using a recursive traversal. At each node:

1. Compute the maximum height of its left subtree (LH).
2. Compute the maximum height of its right subtree (RH).
3. Add them together (LH + RH) and update a global maximum variable (maxi).

The Flaw: Skewed Trees and Redundant Traversals

While this logic is correct, its time complexity is inefficient.

• Traversing all nodes takes $O(N)$ time.
• For each node, calculating its left height and right height independently takes up to $O(N)$ time in the worst-case scenario (e.g., a completely skewed tree where nodes form a single linear chain).
• This results in an overall time complexity of $O(N^2)$, which is unacceptable for large production systems.

4. Step-by-Step Evolution to an Optimized $O(N)$ Solution

To optimize our solution down to $O(N)$, we must eliminate redundant height calculations.

Observe what happens during a standard post-order traversal used to find the height of a tree:

1. When computing the height at any junction (node), we already naturally compute both its left height (LH) and right height (RH) to return 1 + max(LH, RH).
2. Instead of running separate functions to find heights, we can piggyback on the standard height-finding recursion.
3. As LH and RH are calculated on-the-fly for every node, we instantly evaluate LH + RH and update our global maxi tracker.

5. Complete Flow Walkthrough (Dry Run)

Let's trace how the optimized height-and-diameter function evaluates a tree:

1. Base Case: If a node is null, it returns a height of 0.
2. Recursive Step: Fetch leftHeight from the left child and rightHeight from the right child.
3. Max Update: Compare maxi with leftHeight + rightHeight, and update maxi if the current sum is greater.
4. Height Return: Return the standard height for the current node: 1 + max(leftHeight, rightHeight).

6. Implementation Code (C++ and Java)

Below are the production-ready implementations in both C++ and Java.

C++ Implementation

In C++, we can easily pass the maximum diameter variable by reference (int& maxi) alongside a standard post-order height calculation.

class Solution {
private:
    int height(TreeNode* root, int& maxi) {
        if (root == nullptr) {
            return 0;
        }
        
        int leftHeight = height(root->left, maxi);
        int rightHeight = height(root->right, maxi);
        
        // Update diameter at the current node
        maxi = max(maxi, leftHeight + rightHeight);
        
        // Return standard height of the current subtree
        return 1 + max(leftHeight, rightHeight);
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        int maxi = 0;
        height(root, maxi);
        return maxi;
    }
};

Java Implementation

Java does not support primitive pass-by-reference. To work around this limitation, we use a single-element integer array (int[] maxi = new int[1]) to maintain mutable state across recursive stack frames.

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        int[] maxi = new int[1];
        height(root, maxi);
        return maxi[0];
    }
    
    private int height(TreeNode node, int[] maxi) {
        if (node == null) {
            return 0;
        }
        
        int leftHeight = height(node.left, maxi);
        int rightHeight = height(node.right, maxi);
        
        // Update the maximum diameter found so far
        maxi[0] = Math.max(maxi[0], leftHeight + rightHeight);
        
        // Return height of the current node
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Definition Mastery: The diameter of a binary tree is the longest path between any two nodes, which does not necessarily pass through the root.
• The Core Formula: For any node, the longest path passing through it is always Left Height + Right Height.
• Avoiding Redundancy: Naive approaches calculate heights repeatedly, leading to a sluggish $O(N^2)$ runtime.
• Single-Traversal Optimization: By computing diameter calculations inside the standard recursive height function, we drop time complexity down to $O(N)$.
• Language Nuances: In C++, pass variables by reference (int&); in Java, utilize single-element arrays (int[]) or wrapper objects to achieve pass-by-reference behavior for primitive states.