Diameter of a Binary Tree: Answers That Bypass the Root

If you interview at Meta, Amazon, Google, expect some version of "Diameter of Binary Tree". It is rated Easy, and it falls squarely into the Tree DFS pattern — pattern-first preparation beats grinding random problems every time. Part 7 of 11 in the Tree DFS arc.

The Problem

Return the diameter: the number of edges on the longest path between any two nodes, which need not pass through the root. Deceptively labeled easy — it introduces the return-one-track-another shape that Maximum Path Sum turns into a hard question.

Input:  root = [1, 2, 3, 4, 5]
Output: 3
The path 4 -> 2 -> 5 (or 4 -> 2 -> 1 -> 3) has three edges.

Recognizing the Tree DFS Pattern

Depth-first search commits to one branch before trying siblings — recursion (or an explicit stack) whose call structure mirrors the tree itself. Its natural questions are about paths (root to leaf), subtree properties (computed bottom-up from children), and exhaustive exploration (islands, connected regions). The recurring design decision is what each recursive call returns versus what it accumulates in shared state.

The candidate answer at each node (left height plus right height) is not what the recursion can return upward (a path through a parent can only use one side). Whenever those two quantities differ, the shape is: return the extendable value, update a nonlocal best with the local combination.

The Approach

One post-order helper returns subtree height; at each node it updates a running best with left-height plus right-height. Parents receive 1 + max(heights) — the only thing extendable through them.

Calling height() separately per node is the O(n²) trap; fusing the height computation with the best-tracking is what makes it O(n), and articulating that fusion is the interview.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


def diameter_of_binary_tree(root: TreeNode | None) -> int:
    """Edges on the longest node-to-node path."""
    best = 0

    def height(node: TreeNode | None) -> int:
        nonlocal best
        if node is None:
            return 0
        lh = height(node.left)
        rh = height(node.right)
        best = max(best, lh + rh)          # path bending at this node
        return 1 + max(lh, rh)             # only one arm extends upward

    height(root)
    return best

Complexity

• Time: O(n) — single post-order pass computes heights and best together
• Space: O(h) — recursion stack

Interview Tips and Follow-Ups

• Edges vs nodes: this counts edges; some phrasings count nodes (answer plus one). Clarify before coding — it is a deliberate ambiguity.
• nonlocal vs returning a (height, best) tuple: both fine; pick one and be fluent. Instance variables on a class are the LeetCode-ism.
• Say explicitly why the naive version is O(n²) (height recomputed per node) — diagnosing the slow solution is part of the question.

More Tree DFS problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.