LeetCode Maximum Depth of Binary Tree: DFS in 3 Lines

Intermediate 8 min read

What you'll learn

✓How to compute tree depth recursively
✓Why the base case returns 0 instead of 1
✓How to compute depth iteratively with BFS level counting
✓Tradeoffs between DFS recursion and BFS iteration
✓How to articulate the invariant cleanly in interviews

Prerequisites

•Read [Binary Trees Introduction](/blog/binary-trees-introduction) for node basics
•Read [Binary Trees Traversals](/blog/binary-trees-traversals) for DFS and BFS templates

LeetCode 104 Maximum Depth of Binary Tree is rated Easy and is the canonical example of recursive tree thinking. If you can confidently explain why the answer is 1 + max(left_depth, right_depth), you have the foundation for nearly every other tree DP problem on the platform.

The Problem

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

Example:

Input:      3
           / \
          9   20
              / \
             15  7

Output: 3

The empty tree has depth 0.

Brute Force

There is no meaningful brute force; the recursive solution is already optimal. One unnecessarily verbose approach collects every root-to-leaf path and takes the maximum length.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth_paths(root):
    if not root:
        return 0
    paths = []

    def dfs(node, depth):
        if not node.left and not node.right:
            paths.append(depth)
            return
        if node.left:
            dfs(node.left, depth + 1)
        if node.right:
            dfs(node.right, depth + 1)

    dfs(root, 1)
    return max(paths)

Runs in O(n) but allocates an extra list. We do not need to remember the paths to know the max.

Optimal Solution

The recursive solution is three lines.

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

The iterative BFS version counts levels.

from collections import deque

def max_depth_bfs(root):
    if not root:
        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

Both run in linear time.

Walk Through an Example

Use:

max_depth(3) returns 1 + max(max_depth(9), max_depth(20)).

max_depth(9): node 9 has no children, so each recursive call into None returns 0. Result: 1 + max(0, 0) = 1.

max_depth(20): recurses into 15 and 7. Each returns 1 by the same reasoning. Result: 1 + max(1, 1) = 2.

Back at the root: 1 + max(1, 2) = 3. Correct.

For the BFS version, the queue processes level 1 (just 3), then level 2 (9 and 20), then level 3 (15 and 7). The loop increments depth three times. Same answer.

Edge Cases

Empty tree: root is None. The base case returns 0. The problem defines empty depth as 0, not 1.
Single node: depth 1. Both children are None, so 1 + max(0, 0) = 1.
Completely skewed tree (linked list): depth equals the number of nodes. Recursion depth can hit Python’s default limit of 1000 around there; mention switching to iterative if asked about scale.
Very wide tree: BFS uses more memory at the widest level; DFS uses O(h) stack space.

Complexity Analysis

Time: O(n). Every node is visited exactly once.
Space recursive DFS: O(h) for the call stack, where h is the height. Worst case O(n) for a skewed tree.
Space iterative BFS: O(w) for the queue, where w is the maximum level width. Worst case O(n / 2) for a balanced tree.

How to Explain It in an Interview

State the recursive definition: the depth of a tree rooted at X is 1 plus the larger of the depths of its left and right subtrees. The empty tree has depth 0. That is the entire algorithm. The base case is critical because it lets the addition of 1 at each level count exactly one node per level.

If asked which approach to prefer, point out that DFS recursion is concise and natural for this question, while BFS is preferred if the interviewer extends the problem to “return all nodes at the deepest level” or “minimum depth”, where BFS short-circuits earlier.

When asked about complexity, mention both the time bound and the space bound, and note that recursion stack depth depends on tree height, not node count, except for skewed trees where they coincide.

LeetCode 111 Minimum Depth of Binary Tree, where BFS is genuinely faster.
LeetCode 543 Diameter of Binary Tree, which extends this pattern.
LeetCode 110 Balanced Binary Tree, which uses depth as a building block.
LeetCode 226 Invert Binary Tree for another recursive transformation.

Wrap up

Maximum Depth is the cleanest possible example of recursion on a tree. Once you can write it in three lines without thinking, attempt Diameter of Binary Tree, which reuses the same DFS but tracks a global maximum. For a deeper review of traversal patterns, revisit Binary Trees Traversals.