Maximum Depth of Binary Tree — DFS in Three 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

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

Maximum Depth of a Binary Tree 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.

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. The empty tree has depth 0.

Example:

Input:      3
           / \
          9   20
              / \
             15  7

Output: 3

Intuition

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. The base case is critical because it lets the addition of 1 at each level count exactly one node per level. An iterative BFS counts levels instead — increment a counter every time you process a full level of the queue.

Explanation with Example

Use:

maxDepth(3) returns 1 + max(maxDepth(9), maxDepth(20)). maxDepth(9): node 9 has no children, so each recursive call into None returns 0. Result: 1 + max(0, 0) = 1. maxDepth(20): recurses into 15 and 7. Each returns 1. Result: 1 + max(1, 1) = 2. Back at the root: 1 + max(1, 2) = 3. Correct.

For BFS, 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.

         3   (returns 1 + max(1,2) = 3)
      / \
 (1) 9   20  (returns 1 + max(1,1) = 2)
        /  \
   (1) 15   7 (1)

return values flow upward:
leaves return 1
20 returns 1 + max(1,1) = 2
3  returns 1 + max(1,2) = 3

DFS depth bubbles up: each node returns 1 + max(left, right)

Code

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


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

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

public int maxDepthBfs(TreeNode root) {
    if (root == null) return 0;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    int depth = 0;
    while (!q.isEmpty()) {
        depth++;
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }
    return depth;
}

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}

int maxDepthBfs(TreeNode* root) {
    if (!root) return 0;
    std::queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        depth++;
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return depth;
}

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.

Minimum Depth of Binary Tree, where BFS is genuinely faster.
Diameter of Binary Tree, which extends this pattern.
Balanced Binary Tree, which uses depth as a building block.
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.