Trees crash course ↗ · 143

543. Diameter of Binary Tree

The diameter of a binary tree is the longest path (in edges) between any two nodes — it need not pass through the root. A single post-order DFScomputes every node's height and, as a by-product, updates a best counter with leftEdges + rightEdges at every node.

● EasyDFS / Post-orderTree HeightGlobal State in RecursionTypeScript

PROBLEM What we're solving

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

Example: 1,2,3,4,5: the tree looks like

      1
     / \
    2   3
   / \
  4   5
The longest path is 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3, both with 3 edges. Answer: 3.

KEY IDEA Height returns upward; diameter records sideways

Insight → At every node, the longest path through that node equals the number of edges going left plus the number going right. That is leftEdges + rightEdges. Run a post-order DFS that returns height upward but updates a global best sideways. One pass, no extra data structure.

RECIPE Post-order height + global best

  • 0 · Base case. A null node has height -1(using the "-1 for null" convention makes the edge-count arithmetic clean: a leaf has height 0, so a single edge to it is 0 + 1 = 1).
  • 1 · Recurse left and right.Because we need both children's heights before we can evaluate the current node, this is post-order (left → right → node).
  • 2 · Compute edge counts. leftEdges = node.left !== null ? leftH + 1 : 0. A null child contributes 0 edges, not -1 + 1 = 0 (same math, but explicit is safer).
  • 3 · Update global best. best = Math.max(best, leftEdges + rightEdges). This captures the diameter through every possible "turning point" in the tree.
  • 4 · Return height. return Math.max(leftH, rightH) + 1. This is what the parent node needs to compute its own edge counts.
Classic confusion → Returning height upward while updating bestas a side-effect feels wrong — the function seems to do two things at once. It's fine: the return value serves the parent; the side-effect serves the global answer. These are two different questions. The key discipline is never return the candidate diameter — always return height.

COST Complexity & alternatives

Naive: height() per node
O(n²)
Recomputes subtree heights from scratch for each node.
Post-order DFS (this)
O(n)
Each node visited exactly once; O(h) stack space.

Space note

The recursion stack is O(h) where h is the tree height — O(log n) for a balanced tree, O(n) in the worst case (a skewed chain). An iterative post-order with an explicit stack achieves the same time at O(n) space, but the recursive form is cleaner to read and usually fine in interviews.

Pattern transfer →The "return one thing, update global with another" pattern appears throughout tree problems: Binary Tree Maximum Path Sum (return gain, update best sum), Longest Univalue Path (return univalue arm length, update best), and Balanced Binary Tree (return height, update a flag). Recognizing this split makes all of them easy.

RUN IT Post-order DFS: track leftEdges + rightEdges at every node

step 0 / 13
STARTPost-order DFS: visit left and right subtrees before the current node.
1▶function diameterOfBinaryTree(root: TreeNode | null): number {
2▶  let best = 0;
3 
4▶  function height(node: TreeNode | null): number {
5    if (node === null) return -1;          // null child contributes -1 height
6 
7    const leftH  = height(node.left);
8    const rightH = height(node.right);
9 
10    // edges to left/right subtrees (0 when child is absent)
11    const leftEdges  = node.left  !== null ? leftH  + 1 : 0;
12    const rightEdges = node.right !== null ? rightH + 1 : 0;
13 
14    best = Math.max(best, leftEdges + rightEdges);
15 
16    return Math.max(leftH, rightH) + 1;   // height of this node
17  }
18 
19  height(root);
20  return best;
21}
12345
State
0
best
0
diameter
—
leftH
—
rightH
—
leftEdges
—
rightEdges
current nodeheight computedbest diameter path
slowfast

TYPESCRIPT The solution, annotated

diameterOfBinaryTree.ts
function diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;

  function height(node: TreeNode | null): number {
    if (node === null) return -1;          // null child contributes -1 height

    const leftH  = height(node.left);
    const rightH = height(node.right);

    // edges to left/right subtrees (0 when child is absent)
    const leftEdges  = node.left  !== null ? leftH  + 1 : 0;
    const rightEdges = node.right !== null ? rightH + 1 : 0;

    best = Math.max(best, leftEdges + rightEdges);

    return Math.max(leftH, rightH) + 1;   // height of this node
  }

  height(root);
  return best;
}

Reading it block by block

Line 2 — outer mutable. bestis declared in the outer scope so the inner recursive function can update it without passing it around. This is the standard pattern for a "global best" in tree DFS.
Line 4 — base case. null returns -1. Using -1 (not 0) means a leaf node returns Math.max(-1,-1)+1 = 0, and the edge to that leaf is 0+1 = 1. It keeps the arithmetic consistent without any special-casing.
Lines 6–7 — post-order recurse. Left and right children are fully processed before we evaluate the current node. This is the defining property of post-order and is required because we need both heights before computing the candidate diameter.
Lines 9–10 — edge counts. leftEdges is leftH + 1 if a left child exists, else 0. Null children contribute 0 edges to the path, not a negative number — the explicit guard prevents accidental -1+1=0 bugs when the convention is later changed.
Line 12 — update best. The candidate diameter through this node is leftEdges + rightEdges. Taking the max over every node in the tree finds the overall diameter, even when it passes through a non-root node.
Line 14 — return height. The caller needs the height of this subtree to compute its own edge counts. Height = length of the longest path from this node down to a leaf. Math.max(leftH, rightH) + 1 picks the taller child and adds 1 for the edge connecting this node to it.
Complexity → O(n) time — each node is visited exactly once in the DFS. O(h) stack space for recursion, where h = tree height. For a balanced tree h = O(log n); for a degenerate (linked-list) tree h = O(n).

INTERVIEWFollow-ups they'll ask

  • "Return the actual path, not just the length?" Track the two deepest leaf IDs on each side at the best node. Store parent pointers during the DFS, then trace back from each leaf.
  • "What if it's a weighted tree (edges have costs)?" Return the total cost of the deepest path from each subtree instead of just the edge count. The update rule becomes best = Math.max(best, maxLeftCost + maxRightCost).
  • "Binary Tree Maximum Path Sum (LC 124)?"Same structure — return the max "gain" (not sum) upward (clamped at 0 so you can ignore negative branches), update best = Math.max(best, node.val + leftGain + rightGain).
  • "Can you do it iteratively?"Yes — iterative post-order using an explicit stack computes heights bottom-up. It's more code but avoids stack-overflow on pathological inputs (100 000-node chains).
  • "What if the tree can have cycles?" That makes it a graph; use BFS/DFS with a visited set. The two-BFS approach (BFS from any node to find a far endpoint, then BFS from that endpoint) finds the diameter in O(V+E).

OPTIMAL DFS / Post-order

diameterOfBinaryTree.ts
function diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;

  function height(node: TreeNode | null): number {
    if (node === null) return -1;          // null child contributes -1 height

    const leftH  = height(node.left);
    const rightH = height(node.right);

    // edges to left/right subtrees (0 when child is absent)
    const leftEdges  = node.left  !== null ? leftH  + 1 : 0;
    const rightEdges = node.right !== null ? rightH + 1 : 0;

    best = Math.max(best, leftEdges + rightEdges);

    return Math.max(leftH, rightH) + 1;   // height of this node
  }

  height(root);
  return best;
}
Complexity → O(n) time — each node is visited exactly once in the DFS. O(h) stack space for recursion, where h = tree height. For a balanced tree h = O(log n); for a degenerate (linked-list) tree h = O(n).

ALT 1 Brute force — recompute height at every node

O(n²) time · O(h) space

For each node, the diameter through it is height(left) + height(right) + 2. Call a separate heighthelper at every node and take the max — the literal definition, no shared state.

approach-2.ts
function diameterOfBinaryTree(root: TreeNode | null): number {
  // Plain height: longest downward path in edges (null = -1, leaf = 0).
  function height(node: TreeNode | null): number {
    if (node === null) return -1;
    return Math.max(height(node.left), height(node.right)) + 1;
  }

  let best = 0;
  function visit(node: TreeNode | null): void {
    if (node === null) return;
    // Diameter through this node = edges down-left + edges down-right.
    const through = height(node.left) + height(node.right) + 2;
    best = Math.max(best, through);
    visit(node.left);
    visit(node.right);
  }

  visit(root);
  return best;
}
Note → Every node calls height, which itself walks that node's whole subtree — so subtree heights are recomputed over and over, giving O(n²) on a skewed tree. The post-order solution returns the height while updating best, collapsing both jobs into a single O(n) pass.

MNEMONIC The one-liner

"Height goes up the call stack; diameter stays sideways in best. Return one, record the other."

TRIGGERS When you see ___ → reach for ___

"longest path between any two nodes"post-order DFS, leftEdges+rightEdges
"tree path not through root"global best updated at each node
"return height, update global"the height-with-side-effect pattern
"Binary Tree Max Path Sum"same skeleton, return gain not sum

SKELETON The reusable shape

skeleton.ts
let best = 0;

function height(node: TreeNode | null): number {
  if (node === null) return -1;

  const leftH  = height(node.left);
  const rightH = height(node.right);

  const leftEdges  = node.left  !== null ? leftH  + 1 : 0;
  const rightEdges = node.right !== null ? rightH + 1 : 0;
  best = Math.max(best, leftEdges + rightEdges);

  return Math.max(leftH, rightH) + 1;
}

height(root);
return best;

FLASHCARDS Tap to flip

What does the inner function return vs. update?
Returns heightupward (for the parent's edge calculation). Updates best sideways (the diameter through this node).
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
For the tree 1,2,3,4,5 (the worked example), what is the diameter?
QUESTION 02
Why does the helper function return height, not the candidate diameter?
QUESTION 03
What is the time complexity of the post-order DFS approach?
QUESTION 04
A null node returns -1 from the height function. Why not 0?
QUESTION 05
What is the worst-case space complexity and when does it occur?
QUESTION 06
A single-node tree (just the root) has diameter:
QUESTION 07
Which of these best describes the "diameter at node X"?
QUESTION 08
#543 · Diameter of Binary TreePost-order DFS returns the height of each subtree. The diameter through any node equals leftHeight + rightHeight; a global variable tracks the maximum across all nodes, giving O(n).Which algorithmic approach does this primarily use?
QUESTION 09
#543 · Diameter of Binary TreePost-order DFS returns the height of each subtree. The diameter through any node equals leftHeight + rightHeight; a global variable tracks the maximum across all nodes, giving O(n).Which implementation correctly solves it?