Maximum Depth of a Binary Tree: DFS in Four Lines

This one is a Easy-rated classic reported from Amazon, Google, Apple interviews: "Maximum Depth of Binary Tree". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Tree DFS pattern on sight. Part 1 of 11 in the Tree DFS arc.

The Problem

Return the maximum depth — the number of nodes on the longest path from root to leaf. Everyone solves it; the interview value is how you frame it, because the framing (a subtree's answer from its children's answers) scales to genuinely hard questions like Maximum Path Sum.

Input:  root = [3, 9, 20, None, None, 15, 7]
Output: 3

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.

Depth of a tree is one plus the larger child depth, with the empty tree contributing zero — a property defined recursively on subtrees. When the definition is recursive, the DFS is the definition transcribed.

The Approach

Base case: None has depth 0. Recursive case: 1 + max(depth(left), depth(right)). State it, write it, and add the two things interviewers push on: the recursion depth equals tree height (O(n) stack on a degenerate chain), and the iterative rewrite uses an explicit stack of (node, depth) pairs.

For a warm-up like this, volunteering the recursion-limit caveat in Python (default around 1000) converts a trivial answer into a memorable one.

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 max_depth(root: TreeNode | None) -> int:
    """Nodes on the longest root-to-leaf path."""
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Complexity

• Time: O(n) — every node is visited once
• Space: O(h) — recursion stack equals tree height — O(log n) balanced, O(n) degenerate

Interview Tips and Follow-Ups

• Say O(h), not O(log n), for stack space unless the tree is stated balanced — precision here is a known calibration point.
• Iterative version: stack of (node, depth) with a running max — write it once so it is available when an interviewer bans recursion.
• Contrast with Minimum Depth (BFS arc): max needs the whole tree, min rewards early exit. Choosing the traversal per problem is the actual skill.

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.