Diameter of Binary Tree — LC 543 Tree DP Height Trick Interview Guide

Problem Statement#

Given the root of a binary tree, return the length of the diameter — the longest path (in edges) between any two nodes in the tree. The path may or may not pass through the root.

Constraints:

• Number of nodes is in range 1 to 10000
• Node values fit in 32-bit signed integer range
• Diameter is measured in edges, not nodes

Input:  root = [1,2,3,4,5]
Output: 3
Explanation: longest path 4 -> 2 -> 1 -> 3 has 3 edges.

Input:  root = [1,2]
Output: 1

Why This Problem Matters#

LeetCode 543 Diameter of Binary Tree is the gateway problem to Tree DP — a pattern where each recursive call returns one value (height) while updating a global answer (diameter) using values from both subtrees. Amazon, Meta, Google, Apple, and Bloomberg ask this regularly, often as a warmup before LC 124 Binary Tree Maximum Path Sum.

The conceptual hurdle is the dual-purpose recursion. The function returns the height of the subtree (so the parent can use it), but it also records the candidate diameter (left height + right height) into a shared variable along the way. Mixing return value and side effect cleanly is the senior-level skill on display.

The label says Easy on LeetCode, but in interviews it functions as a Medium because candidates often try to compute height twice (once for diameter, once for recursion) which gives O(n^2). Recognizing the single-pass trick is the actual signal.

The Core Insight#

The diameter of a tree is the longest path between any two leaves (or any two nodes). At every node, the longest path passing through that node is left_height + right_height (in edges). The overall diameter is the maximum such value across all nodes.

To compute heights and diameters in one pass, define depth(node):

1. If node is null, return 0.
2. Recurse to get left_h = depth(node.left) and right_h = depth(node.right).
3. Update global answer: ans = max(ans, left_h + right_h).
4. Return max(left_h, right_h) + 1 so the parent can use this height.

Each node is visited once. The trick is that the answer (diameter) is computed from values children return, but the function itself returns height to the parent.

Visual Dry Run#

Tree: 1 -> {2 -> {4, 5}, 3}.

Final diameter is 3 edges, matching path 4 -> 2 -> 1 -> 3.

Solution (Optimal)#

class Solution:
    def diameterOfBinaryTree(self, root):
        self.ans = 0
 
        def depth(node):
            if not node:
                return 0
            left_h = depth(node.left)
            right_h = depth(node.right)
            self.ans = max(self.ans, left_h + right_h)
            return max(left_h, right_h) + 1
 
        depth(root)
        return self.ans

var diameterOfBinaryTree = function(root) {
    let ans = 0;
 
    const depth = (node) => {
        if (!node) return 0;
        const leftH = depth(node.left);
        const rightH = depth(node.right);
        ans = Math.max(ans, leftH + rightH);
        return Math.max(leftH, rightH) + 1;
    };
 
    depth(root);
    return ans;
};

Time: O(n) — every node is visited exactly once. Space: O(h) — recursion stack proportional to tree height; O(log n) balanced, O(n) skewed.

Common Mistakes#

• Computing height in one pass and diameter in a second pass — gives O(n^2) instead of O(n)
• Counting nodes instead of edges — diameter is one less than node count
• Returning left_h + right_h from depth instead of max(left_h, right_h) + 1
• Forgetting to update the global answer before returning, missing diameters that pass through this node
• Initializing ans to 1 instead of 0 — fails on a single-node tree where diameter is 0

Interview Tips#

• Explicitly explain the dual-purpose recursion: "this function returns height but also updates the global diameter as a side effect"
• State the invariant: "longest path through any node equals left height plus right height"
• Mention LC 124 Binary Tree Maximum Path Sum as the same Tree DP pattern with a twist (clip negative subtree contributions)
• For follow-ups asking the actual nodes on the diameter, reconstruct from a parent map after the height pass

Follow-up Questions#

• Return the list of nodes on the diameter path — do height pass first, then reconstruct
• Diameter of an N-ary tree — compute height of each child, take top two heights, sum
• Diameter of a general undirected tree — root anywhere, run two BFS passes (tree-diameter trick)
• Weighted edges — same recursion, replace +1 with edge weight

Key Takeaways#

• LeetCode 543 Diameter of Binary Tree is the canonical Tree DP entry point at Amazon, Meta, Google, and Bloomberg
• Time is O(n) single-pass; space is O(h) for recursion
• Pattern: return height from the recursive call, update a global diameter as a side effect
• Diameter at any node equals left subtree height plus right subtree height, measured in edges
• A two-pass solution (height then diameter) is O(n^2) and a common mistake
• Same Tree DP template scales to LC 124 Binary Tree Max Path Sum and LC 1245 Tree Diameter for general trees
• Single-node tree has diameter 0; never initialize the answer to 1