Maximum Depth of Binary Tree — LeetCode 104 Recursive DFS Walkthrough

Problem Statement#

Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from the root node down to the farthest leaf node.

Constraints:

• Number of nodes in the tree is in the range [0, 10^4].
• -100 <= Node.val <= 100.

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

Input:  root = [1,null,2]
Output: 2

Why This Problem Matters#

LeetCode 104 — Maximum Depth of Binary Tree is the single most common warmup question at FAANG phone screens. Amazon, Google, Meta, Apple, and Microsoft all use it as a five-minute opener before moving to a harder follow-up. It is the canonical "first tree problem" because it reveals whether the candidate truly understands recursion before they reach LCA, diameter, or path sum.

Although it is rated Easy, recruiters watch for three things: a clean base case, the recursive contract, and the ability to discuss BFS as an alternative. Candidates who blank on the base case lose the entire signal in seconds. This is exactly why you should over-prepare it.

The problem also forms the backbone of Balanced Binary Tree (LC 110), Diameter of Binary Tree (LC 543), and Maximum Path Sum (LC 124). Master this one and you shortcut the entire tree-DP family.

The Core Insight#

The depth of any tree equals 1 plus the maximum depth of its two subtrees. That recursive contract is the entire algorithm — every node returns its own subtree depth and the parent picks the max.

The base case is the empty tree, which has depth 0. Once you write if not root: return 0, the rest writes itself: return 1 + max(depth(left), depth(right)).

This is the prototype for every tree-DP problem you will ever solve. The pattern is: solve the subproblem on root.left, solve it on root.right, combine the two answers, return one number.

Visual Dry Run#

Tree: [3,9,20,null,null,15,7]

The longest path is 3 -> 20 -> 15 (or 3 -> 20 -> 7), three nodes deep, so the answer is 3.

Solution (Optimal)#

# Python — recursive DFS, the textbook one-liner expanded for clarity
class Solution:
    def maxDepth(self, root):
        if not root:
            return 0  # empty subtree has depth 0
        # +1 accounts for the current node itself
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

// JavaScript — same recursion, terse
var maxDepth = function(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

# Iterative BFS alternative — useful if interviewer asks for non-recursive
from collections import deque
class Solution:
    def maxDepth(self, root):
        if not root: return 0
        q, depth = deque([root]), 0
        while q:
            depth += 1
            for _ in range(len(q)):
                n = q.popleft()
                if n.left:  q.append(n.left)
                if n.right: q.append(n.right)
        return depth

Time: O(n) — every node is visited exactly once. Space: O(h) for recursion stack (worst case O(n) for a skewed tree, O(log n) for a balanced tree). BFS uses O(w) where w is the max width.

Common Mistakes#

• Returning 0 for a single-node tree. A single node has depth 1, not 0 — the if not root: return 0 base only fires when the child is null.
• Confusing depth with height of edges; LeetCode 104 counts nodes on the path, not edges.
• Using max(left, right) + 1 order swap that accidentally evaluates wrong subtree first when there are side effects.
• Writing iterative BFS without tracking level boundaries — that returns total node count, not depth.

Interview Tips#

• State the recursive contract out loud: "depth of a node equals 1 plus the max of its children's depths".
• Sketch a 3-level tree on the whiteboard and dry-run two recursive calls.
• Mention both DFS and BFS variants; pick DFS for brevity but offer BFS if the interviewer asks about non-recursive solutions.
• Bring up tail-recursion / stack overflow risk for very deep trees in production code.

Follow-up Questions#

• Minimum depth (LC 111)? Same template but careful when one child is null — return the non-null side's depth, not 1.
• Balanced tree check (LC 110)? Postorder return both height and a balanced flag.
• N-ary tree depth (LC 559)? Replace left/right with a max over children.
• Iterative without recursion? BFS with level counter, or DFS with explicit stack of (node, depth).
• Can you do it in O(1) extra space? Only with Morris traversal, which is overkill for this problem.

Key Takeaways#

• LeetCode 104 Maximum Depth of Binary Tree runs in O(n) time and O(h) space with recursive DFS.
• The recursive contract is depth(root) = 1 + max(depth(left), depth(right)) with base case 0 for null.
• This is the prototype for every tree-DP problem: diameter, max path sum, balanced tree, house robber III.
• BFS with level counting is the iterative alternative — same O(n) time, O(w) space for max width.
• Asked at Amazon, Google, Meta, Apple, Microsoft as a warmup before harder tree questions.
• A single-node tree has depth 1, not 0 — the base case fires on null children, not the root.
• Always mention the recursion stack risk for skewed trees in a production discussion.