dfs(3)
call
The maximum depth of a binary tree is the length of the longest root-to-leaf path. A single post-order DFS computes it in one pass: each node returns 1 + max(leftDepth, rightDepth), bubbling the answer up to the root.
Given the root of a binary tree, return the number of nodes along the longest path from the root to the farthest leaf. A single node has depth 1; an empty tree has depth 0.
Example: 3,9,20,null,null,15,7 — the root is 3, its left subtree has depth 1 (just node 9), its right subtree has depth 2 (nodes 20→15 or 20→7). The maximum depth is 3.
1 + max(left, right) propagates the answer from the leaves to the root automatically. Every node answers a single small question — the recursion does the rest.root === null, return 0. An empty subtree contributes zero depth.maxDepth(root.left) to get the depth of the left subtree.maxDepth(root.right) to get the depth of the right subtree.1 + Math.max(leftDepth, rightDepth). The +1 counts the current node; max picks the taller child.Math.max(left, right) without the +1 undercounts by 1 for every non-null node. The current node itself is a level — always add 1 before returning.Level-order BFS with a queue also works: process the tree level by level, incrementing a counter each time the queue drains a full level. The answer is the number of levels. Same O(n) time, but O(w) space where w is the maximum width (can be O(n) for a wide tree, vs O(h) for DFS on a balanced tree).
1 + max(left, right) backbone powers Diameter of Binary Tree (track max(left+right) on the side), Balanced Binary Tree (return −1 if |left−right| > 1), and Binary Tree Maximum Path Sum (replace max-depth arithmetic with path sums).3. We'll recurse left then right, then return 1 + max(leftDepth, rightDepth) at each node.function maxDepth(root: TreeNode | null): number {
if (root === null) return 0; // base case: empty tree
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return 1 + Math.max(leftDepth, rightDepth);
}null node (empty subtree) has depth zero. This is what stops the recursion at leaves and beyond.1 + Math.max(leftDepth, rightDepth). The 1 accounts for the current node; Math.max picks the taller child. The answer naturally bubbles up to the root.if (!left) return 1 + right and vice versa, otherwise a skewed tree returns 1 incorrectly.max(left + right) in a closure variable during the same DFS. Each node contributes a candidate path through itself (left + right edges), while still returning 1 + max(left, right) to its parent.-1 (sentinel) instead of the depth whenever |leftDepth - rightDepth| > 1. Propagate the sentinel upward; O(n) single pass.| longest root-to-leaf path | post-order DFS, return 1 + max(left, right) |
| "height" or "depth" of a tree | base case null → 0, else recurse both sides |
| need per-subtree answer before parent | post-order pattern (left, right, root) |
| depth + extra metric (diameter, balance) | same DFS + closure variable for extra info |
function maxDepth(root: TreeNode | null): number {
if (root === null) return 0;
const left = maxDepth(root.left);
const right = maxDepth(root.right);
return 1 + Math.max(left, right);
}null node → return 0. An empty subtree has zero depth.maxDepth called with for the tree 3,9,20,null,null,15,7?return Math.max(left, right) (forgetting the +1). What happens?