Maximum Depth of Binary Tree: Recursion Made Simple

You are given the root of a binary tree. Return its maximum depth, which is the number of nodes along the longest path from the root down to the farthest leaf.

This is LeetCode 104: Maximum Depth of Binary Tree, and it is the single best introduction to tree recursion. If you have never solved a tree problem before, start here. The pattern it teaches (recursive DFS on trees) is the foundation for almost every other tree problem on LeetCode.

Why this problem matters

Most people see trees and immediately feel overwhelmed. There are nodes, pointers, left children, right children, and suddenly everything feels abstract. But tree problems are actually some of the most elegant to solve once you trust the recursion.

Maximum Depth of Binary Tree is where that trust clicks. The solution is three lines of code. And those three lines contain the exact recursive pattern you will use in Validate BST, Symmetric Tree, Invert Binary Tree, Path Sum, and dozens of others.

The key insight

Think about it this way. If someone asks you "how deep is this tree?", you could answer: "Well, it is 1 (for the root) plus whichever subtree is deeper."

That is the whole algorithm. The depth of any tree is:

1. 0 if the tree is empty (null node)
2. 1 + max(depth of left subtree, depth of right subtree) otherwise

That is a recursive definition, and it translates directly into code.

The DFS solution

def max_depth(root):
    if root is None:
        return 0
    left = max_depth(root.left)
    right = max_depth(root.right)
    return 1 + max(left, right)

Three lines of real logic. Let's break them down:

• if root is None: return 0 is the base case. An empty tree has depth 0. This is where every recursive call eventually stops.
• left = max_depth(root.left) recursively computes the depth of the entire left subtree.
• right = max_depth(root.right) does the same for the right subtree.
• return 1 + max(left, right) takes the deeper subtree and adds 1 for the current node.

That is it. You do not need to manually track the depth, manage a counter, or think about the whole tree at once. You just ask each subtree "how deep are you?" and combine the answers.

Visual walkthrough

Let's trace the recursion through the tree [3, 9, 20, null, null, 15, 7] step by step. Watch how each node asks its children for their depth, then combines the results going back up.

Notice the pattern. The recursion goes all the way down to the leaves first, then builds the answer back up as it returns. Node 9 has no children, so both return 0, and it returns max(0, 0) + 1 = 1. Node 20 gets 1 from both children and returns max(1, 1) + 1 = 2. Finally the root gets 1 from the left and 2 from the right, so it returns max(1, 2) + 1 = 3.

This "go down, come back up" flow is how DFS (depth-first search) works on trees. You will see it in every recursive tree problem.

The BFS alternative

You can also solve this with BFS (breadth-first search) using a queue. Instead of recursing down each branch, you process the tree level by level and count how many levels there are.

from collections import deque

def max_depth(root):
    if root is None:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

At each iteration of the while loop, we process one entire level of the tree. We drain everything currently in the queue (that is what the for _ in range(len(queue)) does), adding their children for the next level. Each time we finish a level, we increment depth.

Both DFS and BFS produce the correct answer. The DFS version is shorter, more elegant, and the one you should learn first. BFS is worth knowing because some tree problems (like minimum depth or level-order traversal) are more natural with it.

Complexity analysis

Time is O(n) for both. Every node gets visited exactly once whether you go depth-first or breadth-first.

Space is where they differ. DFS uses O(h) space where h is the height of the tree, because the call stack grows as deep as the longest path. In the worst case (a completely skewed tree that looks like a linked list), h = n and you use O(n) stack space. For a balanced tree, h = log n.

BFS uses O(w) space where w is the maximum width of the tree. For a balanced tree, the bottom level can have up to n/2 nodes, so the queue holds O(n) elements. For a skewed tree, each level has one node, so the queue holds O(1).

In practice, the DFS solution is preferred for this problem. It is simpler, uses less code, and the stack depth is only a concern for extremely deep trees (which LeetCode constraints almost never produce).

Edge cases to watch for

Before submitting, make sure you handle these:

• Empty tree (root is None): return 0. The base case takes care of this.
• Single node (no children): return 1. Both recursive calls return 0, so max(0, 0) + 1 = 1.
• Completely skewed tree (every node has only one child): the tree looks like a linked list. Depth equals the number of nodes. The recursion handles it correctly, but the call stack is O(n).
• Balanced tree: depth is about log(n). This is the best case for stack space.

The building blocks

This problem is built on one fundamental brick: the recursive null base case pattern for trees. The structure looks like this:

def solve(node):
    if node is None:
        return BASE_VALUE
    left = solve(node.left)
    right = solve(node.right)
    return COMBINE(left, right)

For Maximum Depth, BASE_VALUE is 0 and COMBINE is 1 + max(left, right). But the skeleton stays the same across many tree problems. You just change what the base case returns and how you combine the children:

• Minimum Depth (LeetCode 111): same skeleton, but the combine step needs to handle the case where one subtree is empty (you cannot take min(0, something) and say the depth is 1).
• Invert Binary Tree (LeetCode 226): BASE_VALUE is None, and COMBINE swaps left and right children.
• Balanced Binary Tree (LeetCode 110): BASE_VALUE is 0, and COMBINE checks if the height difference between left and right exceeds 1.
• Same Tree (LeetCode 100): two trees, two base cases (both None returns True, one None returns False), and COMBINE is left and right and values match.
• Path Sum (LeetCode 112): BASE_VALUE depends on whether the current node is a leaf, and COMBINE is left or right.

Once you internalize this recursive skeleton, you stop seeing tree problems as intimidating. They are all the same brick with different BASE_VALUE and COMBINE logic.

From understanding to recall

You just read through a three-line solution and a clear visual walkthrough. It makes sense right now. But two weeks from now, when you see Balanced Binary Tree or Path Sum in an interview, will you recognize that it uses the same recursive skeleton? Will you remember that the base case returns 0 and the combine step is 1 + max(left, right)?

Understanding and recall are different skills. You understood the solution. Recall means you can produce it from scratch, under pressure, without a tutorial open in another tab.

Spaced repetition is how you build recall. You practice typing the solution from memory at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the base case, the recursive calls, and the combine step from scratch. After a few repetitions, the recursive null base case pattern is automatic. You do not think about it. You just write it.

The recursive null base case is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is a far more effective strategy than grinding random problems and hoping the patterns stick.

Related posts

• Climbing Stairs - Another recursion-based problem that teaches you how subproblems combine into solutions
• Valid Parentheses - A great companion for understanding stack-based patterns, which are closely related to recursion
• Contains Duplicate - A simple warm-up problem for building your foundation before tackling trees