Diameter of Binary Tree

easyTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(H)
TreesOriginal Statement (leetcode).md

1. Core Invariant / The Trick

In a single bottom-up DFS returning height, any node `u` can serve as the highest turning point of a path of edge length `leftH + rightH`. Maintain `best = max(best, leftH + rightH)` globally while returning `1 + max(leftH, rightH)` upward.

2. Complexity Bounds & Proof

Avoids quadratic repeated height calls by computing both subtree heights and updating the best through-node path in one post-order traversal.

3. Minimal Idiomatic Code

def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:
    best = 0
    def height(node: Optional[TreeNode]) -> int:
        nonlocal best
        if not node:
            return 0
        lh, rh = height(node.left), height(node.right)
        best = max(best, lh + rh)
        return 1 + max(lh, rh)
    height(root)
    return best

4. Failure Modes & Interview Follow-ups

Pitfalls:- Counting nodes instead of edges (diameter is edge count, i.e., `leftH + rightH`). - Assuming the longest path passes through the root.
Follow-ups:- Tree Diameter in a general undirected N-ary graph: run two BFS passes from any node to farthest U, then U to V.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Maximum Depth of Binary Tree (O(N))Binary Tree Maximum Path Sum (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.