Diameter of Binary Tree

LeetCode 543: Diameter of Binary Tree Solution & Explanation

Problem Overview

TL;DR: We solve this by using a Postorder DFS traversal to calculate the height of each node's subtrees, updating the global maximum diameter (left height + right height) as the recursion bubbles up.

The Diameter of Binary Tree problem asks us to find the length of the longest path between any two nodes in a binary tree. The length is defined by the number of edges, not nodes. Importantly, the longest path does not necessarily have to pass through the root of the tree; it can exist entirely within a left or right subtree.

This is a classic LeetCode 543 problem that tests your understanding of tree traversals and recursion state management, making it a popular interview question at major tech companies.

Brute Force Approach for Diameter of Binary Tree

A naive approach relies on the definition that the diameter passing through a specific node is the sum of the maximum depth of its left subtree and the maximum depth of its right subtree.

To solve this via brute force, we could visit every node in the tree. For each node, we would trigger a separate helper function to calculate the maximum depth of its left and right children. We would then sum these depths to find the diameter anchored at that node and compare it to a global maximum.

Pseudo-code:

function diameter(root):
    if root is null: return 0
    
    // Calculate depth of left and right subtrees explicitly
    leftHeight = getDepth(root.left)
    rightHeight = getDepth(root.right)
    
    // Diameter passing through current root
    currentDiameter = leftHeight + rightHeight
    
    // Recurse on children to find if a larger diameter exists elsewhere
    leftDiameter = diameter(root.left)
    rightDiameter = diameter(root.right)
    
    return max(currentDiameter, leftDiameter, rightDiameter)

function getDepth(node):
    if node is null: return 0
    return 1 + max(getDepth(node.left), getDepth(node.right))

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)$.

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.

Pattern Reuse Notes

The Tree DFS - Recursive Postorder Traversal pattern is highly versatile. Understanding how to bubble up information from children to parents applies directly to:

• LeetCode 104: Maximum Depth of Binary Tree - The logic for calculating height is identical to the helper function used here.
• LeetCode 110: Balanced Binary Tree - Uses postorder to check height differences bottom-up.
• LeetCode 124: Binary Tree Maximum Path Sum - Almost identical structure, but instead of summing heights (edges), you sum node values.
• LeetCode 145: Binary Tree Postorder Traversal - The fundamental traversal mechanism used in all these solutions.

Reference Implementation

C++ Solution for LeetCode 543

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13private:
14    int maxDiameter = 0;
15
16    // Helper function returns the height (max depth) of the tree rooted at node
17    int calculateHeight(TreeNode* node) {
18        if (node == nullptr) {
19            return 0;
20        }
21
22        // Postorder traversal: visit children first
23        int leftHeight = calculateHeight(node->left);
24        int rightHeight = calculateHeight(node->right);
25
26        // Update the global maximum diameter
27        // Diameter at this node = left height + right height
28        maxDiameter = std::max(maxDiameter, leftHeight + rightHeight);
29
30        // Return the height of the current node to the parent
31        return 1 + std::max(leftHeight, rightHeight);
32    }
33
34public:
35    int diameterOfBinaryTree(TreeNode* root) {
36        calculateHeight(root);
37        return maxDiameter;
38    }
39};

Java Solution for LeetCode 543

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    private int maxDiameter = 0;
18
19    public int diameterOfBinaryTree(TreeNode root) {
20        calculateHeight(root);
21        return maxDiameter;
22    }
23
24    // Returns the height (number of nodes on longest path down)
25    private int calculateHeight(TreeNode node) {
26        if (node == null) {
27            return 0;
28        }
29
30        // Recursively find heights of left and right subtrees
31        int leftHeight = calculateHeight(node.left);
32        int rightHeight = calculateHeight(node.right);
33
34        // Update the diameter passing through the current node
35        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
36
37        // Return the height of this node to be used by the parent
38        return 1 + Math.max(leftHeight, rightHeight);
39    }
40}

Python Solution for LeetCode 543

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
9        self.max_diameter = 0
10        
11        def height(node):
12            if not node:
13                return 0
14            
15            # Recursive postorder traversal
16            left_height = height(node.left)
17            right_height = height(node.right)
18            
19            # The path through this node is left_height + right_height
20            self.max_diameter = max(self.max_diameter, left_height + right_height)
21            
22            # Return height of the current node
23            return 1 + max(left_height, right_height)
24            
25        height(root)
26        return self.max_diameter