Time Complexity Analysis: The time complexity of this approach is $O(N^2)$ in the worst case (a skewed tree). This is because for every node visited by diameter, we traverse its entire subtree again to calculate getDepth.

• diameter visits $N$ nodes.
• getDepth takes $O(N)$ time.
• Total operations approach $N \times N$.

Why it fails: While correct, $O(N^2)$ is inefficient. With constraints up to $10^4$ nodes, this approach performs redundant calculations. We are recalculating the depth of the same nodes repeatedly. An optimal interview solution requires $O(N)$.

Core Insight for Diameter of Binary Tree

The key intuition for optimizing the LeetCode 543 solution is that the height (or depth) of a node and the diameter passing through that node can be computed in the same traversal.

Every node in a binary tree can be viewed as the "turning point" (or anchor) of a path. The longest path passing through a specific node u is simply the longest leg extending down its left child plus the longest leg extending down its right child.

Instead of calculating depth separately, we can design a dfs function that:

1. Returns the height of the tree rooted at the current node (to be used by its parent).
2. Simultaneously calculates the diameter passing through the current node (left_height + right_height) and updates a global maximum.

By using Postorder Traversal (Left $\to$ Right $\to$ Root), we ensure that when we are at a specific node, we already know the heights of its left and right subtrees. This allows us to compute the diameter for that node in $O(1)$ time and return the height to the parent, resulting in a single $O(N)$ pass.

Visual Description: Imagine the recursion tree expanding until it hits the leaf nodes. As the recursion unwinds (returns), values flow upward. A leaf node reports a height of 1 to its parent. The parent receives heights from both left and right children. It adds them together to check the "local diameter" and updates the global maximum if this sum is the largest seen so far. Then, it adds 1 to the larger of the two child heights and passes that value up to its own parent.

Algorithm Strategy: Tree DFS - Recursive Postorder Traversal

1. Global State: Maintain a variable max_diameter initialized to 0. This tracks the longest path found anywhere in the tree.
2. DFS Function: Create a recursive function that takes a node as input.
   • Base Case: If node is null, return 0. This represents a height of 0.
3. Recursive Step (Postorder):
   • Recursively call the function on node.left and store the result in left_height.
   • Recursively call the function on node.right and store the result in right_height.
4. Process Logic:
   • Calculate the diameter passing through the current node: current_diameter = left_height + right_height.
   • Update the global maximum: max_diameter = max(max_diameter, current_diameter).
5. Return Logic:
   • Return the height of the current node to its parent. The height is 1 + max(left_height, right_height).
6. Result: Start the recursion from the root. Once finished, max_diameter holds the answer.

Execution Flow

Let's trace the execution for root = [1, 2, 3, 4, 5].

1. Call DFS(1): Need DFS(2) and DFS(3). 2. Call DFS(2): Need DFS(4) and DFS(5). 3. Call DFS(4): * Left child is null (returns 0). * Right child is null (returns 0). * Update max_diameter: max(0, 0+0) = 0. * Return height: 1 + max(0, 0) = 1. 4. Call DFS(5): * Left child is null (returns 0). * Right child is null (returns 0). * Update max_diameter: max(0, 0+0) = 0. * Return height: 1 + max(0, 0) = 1.
   • Back at DFS(2):
     • left_height (from 4) is 1.
     • right_height (from 5) is 1.
     • Current path through 2 is 1 + 1 = 2.
     • Update max_diameter: max(0, 2) = 2.
     • Return height: 1 + max(1, 1) = 2.
   5. Call DFS(3):
      • Left/Right are null.
      • Update max_diameter: max(2, 0) = 2.
      • Return height: 1.

• Back at DFS(1):
  • left_height (from 2) is 2.
  • right_height (from 3) is 1.
  • Current path through 1 is 2 + 1 = 3.
  • Update max_diameter: max(2, 3) = 3.
  • Return height: 3.

Final result is 3.

Proof of Correctness

The correctness relies on the property that the longest path in a binary tree must have a unique "highest" node (the node closest to the root that is part of the path). This node acts as the turning point connecting a path in its left subtree and a path in its right subtree.

Our algorithm iterates through every node in the tree using DFS. At every node $u$, we calculate the length of the longest path where $u$ is the highest node (height(u.left) + height(u.right)). Since we check this value for every node and maintain the maximum, we are guaranteed to find the true global diameter.

Reference Implementation

C++ Solution for LeetCode 543

cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int maxDiameter = 0;

    // Helper function returns the height (max depth) of the tree rooted at node
    int calculateHeight(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }

        // Postorder traversal: visit children first
        int leftHeight = calculateHeight(node->left);
        int rightHeight = calculateHeight(node->right);

        // Update the global maximum diameter
        // Diameter at this node = left height + right height
        maxDiameter = std::max(maxDiameter, leftHeight + rightHeight);

        // Return the height of the current node to the parent
        return 1 + std::max(leftHeight, rightHeight);
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        calculateHeight(root);
        return maxDiameter;
    }
};

Java Solution for LeetCode 543

java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int maxDiameter = 0;

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

    // Returns the height (number of nodes on longest path down)
    private int calculateHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // Recursively find heights of left and right subtrees
        int leftHeight = calculateHeight(node.left);
        int rightHeight = calculateHeight(node.right);

        // Update the diameter passing through the current node
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

        // Return the height of this node to be used by the parent
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Python Solution for LeetCode 543

python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = 0
        
        def height(node):
            if not node:
                return 0
            
            # Recursive postorder traversal
            left_height = height(node.left)
            right_height = height(node.right)
            
            # The path through this node is left_height + right_height
            self.max_diameter = max(self.max_diameter, left_height + right_height)
            
            # Return height of the current node
            return 1 + max(left_height, right_height)
            
        height(root)
        return self.max_diameter