Maximum Depth of a Binary Tree: A Step-by-Step Interview Walkthrough

Maximum Depth of a Binary Tree is another short problem that interviewers use as a fundamentals check. Like Invert Binary Tree, the appeal isn't the difficulty — it's that there's nowhere to hide. Can you state the recursive definition cleanly? Can you handle the null case without overcomplicating it? Can you explain why the algorithm is O(n) without hand-waving? The candidate who nails this in two minutes earns credibility for the harder problems that follow. The candidate who fumbles the base case or counts edges instead of nodes signals that they don't have firm foundations.

Computing tree height shows up in self-balancing data structures (AVL and red-black trees rebalance based on height differences), file system depth limits (operating systems cap path nesting to avoid resource exhaustion), DOM tree analysis in browsers (deeply nested HTML hurts render performance), database B-tree maintenance (height determines lookup cost), and any system where hierarchical depth is itself a meaningful metric.

Problem Statement

Given the root of a binary tree, return its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example:

       3
      / \
     9  20
        / \
       15  7

Maximum depth is 3 (the path 3 → 20 → 15 or 3 → 20 → 7).

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.

Input: the root of a binary tree (may be null).

Output: an integer — the maximum depth.

Details to clarify:

• Does depth count nodes or edges? Nodes. A tree with one node has depth 1, not 0.

• What's the depth of an empty tree? 0.

• Can the tree be unbalanced? Yes — no shape guarantees.

• Can the tree be empty? Yes — we handle that with the base case.

• Are node values relevant? No — only the structure matters.

The nodes-vs-edges question is the most important one to ask, because the answer changes the recurrence. If depth were counted by edges, an empty tree would still be 0 but a single-node tree would also be 0.

2. Identify the Category of the Question

A few signals jump out:

• The input is a tree.

• The quantity we want (depth) is defined recursively: a node's depth depends on the depths of its children.

• The work at each node is local — once we know the depths of the two subtrees, we know the depth at the current node.

That combination — tree input, recursive definition, local computation — points immediately to tree recursion, specifically the postorder pattern where each node computes its own answer from its children's answers. Same family as Invert Binary Tree, Diameter of Binary Tree, and Balanced Binary Tree. The structural pattern is compute(node) = f(compute(left), compute(right), node).

3. Brute Force Solution

There isn't really a "brute force" for this problem in the algorithmic sense, but it's worth thinking about a naive approach to understand why the recursive solution is the natural one.

A naive approach: enumerate every root-to-leaf path, measure its length, and take the maximum.

findAllPaths(root) → list of path lengths
return max of the list

The problem here is that a node can appear in many paths if the tree branches a lot. In the worst case (a complete tree), a near-root node appears in near O(n) paths. So this naive approach could blow up to O(n × h) time and requires a lot of bookkeeping for path tracking.

The naive approach reveals an important insight: we don't actually need to track paths. We only need to know, at each node, how deep the longest path below it goes. That's a single number per node, not a list of paths. And that single number has a recursive definition: it's one more than the larger of the two subtree depths.

That observation collapses the path-enumeration problem into a clean per-node calculation.

4. Brainstorm More Solutions

Step 1: Translate the problem definition directly into recursion

The problem statement says: "the maximum depth is the number of nodes along the longest path from the root to the farthest leaf." Let's stare at that for a second and ask what it means recursively.

The longest path from the root has two cases. Either it goes through the left child, or it goes through the right child. (It has to go through one of them — unless there are no children, in which case the path is just the root itself.) So:

maxDepth(node) = 1 + max(maxDepth(left), maxDepth(right))

What about the base case? When node is null, there's no node here to count, so the depth is 0. That's the definition we want, because then a single-node tree gives us 1 + max(0, 0) = 1, which matches "depth counts nodes."

maxDepth(node):
    if node is null: return 0
    return 1 + max(maxDepth(node.left), maxDepth(node.right))

That's the whole algorithm. The recurrence is the same shape as the problem definition — there was no clever transformation, no insight to extract. The problem just is recursive, and we wrote down what it said.

Step 2: Why the base case has to be exactly 0

It's worth pausing on the base case, because it's the easiest line to write wrong and the one most likely to come up in follow-up questions.

If maxDepth(null) = 0, then maxDepth(leaf) = 1 + max(0, 0) = 1. A single leaf has depth 1. That matches "depth counts nodes."

If we accidentally wrote maxDepth(null) = 1, then maxDepth(leaf) = 1 + max(1, 1) = 2. Every leaf would report depth 2, which is wrong.

If we accidentally wrote maxDepth(null) = -1, then maxDepth(leaf) = 1 + max(-1, -1) = 0. That would correspond to counting edges instead of nodes — also a valid definition of depth in some contexts, but not what this problem asked for.

The base case is where the units of measurement get fixed. Pick it carefully, and make sure it matches the problem's definition.

Step 3: What about iteration?

For completeness, we could also do this iteratively with BFS, counting levels:

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        depth++;
    }

    return depth;
}

The trick is the levelSize snapshot at the top of each outer iteration. Before processing a level, we record how many nodes are in the queue — that's the size of the current level. We process exactly that many, adding their children to the queue, then increment depth. When the queue is finally empty, depth is the number of levels processed, which is the maximum depth.

This version is useful when the tree might be deep and the recursive call stack could overflow. It trades stack space (O(h)) for queue space (O(n) in the worst case, where the bottom level has up to n/2 nodes). Heap memory is much larger than stack memory, so for adversarial inputs, this version is safer.

In a normal interview, I'd lead with the recursion.

Step 4: Complexity

The recursive function visits each of the n nodes exactly once and does O(1) work at each (one comparison, one addition). Total time is O(n). Space is O(h) for the call stack, where h is the height of the tree — O(log n) for balanced trees, O(n) for skewed trees.

The iterative BFS version is also O(n) time. Space is O(w) where w is the maximum width of the tree — up to O(n/2) at the bottom of a balanced tree, or O(1) for a skewed tree (since each level has only one node).

There's an interesting trade-off to mention here: for balanced trees, recursion uses less space (O(log n) vs O(n)). For skewed trees, iteration uses less space (O(1) vs O(n)). Most real-world trees fall closer to balanced, which is part of why recursion is the default choice.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Recursive DFS	O(n)	O(h)	My default interview answer — cleanest code, mirrors the recursive definition
Iterative BFS (level-counting)	O(n)	O(w)	If the tree might be deep and stack overflow is a concern
Iterative DFS (stack with depth tracking)	O(n)	O(h)	Rarely worth it — more code than recursion for the same complexity

For a normal interview, recursion wins on clarity and matches the problem's recursive definition. Mention BFS as the safe alternative for deep trees, and you've shown both options without overcomplicating the answer.

6. Pseudocode

maxDepth(node):
    if node is null:
        return 0

    leftDepth = maxDepth(node.left)
    rightDepth = maxDepth(node.right)

    return 1 + max(leftDepth, rightDepth)

That's the entire algorithm. Four lines plus a base case.

7. Edge Cases

Things to verify before claiming we're done:

• Empty tree (null root) → base case returns 0. ✓

• Single-node tree → 1 + max(0, 0) = 1. ✓

• Completely skewed tree (a long chain of left children) → each call adds 1 to the depth from below, returns the correct chain length. Stack depth equals chain length, so very deep chains could risk stack overflow.

• Perfectly balanced tree → recursion visits both sides evenly, returns log₂(n) + 1.

• Tree with one heavy side → the max ensures we measure the longer path, not the shorter one.

The base case handles every degenerate shape without special logic. That's the sign of a clean recursion.

8. Full Code

import java.util.LinkedList;
import java.util.Queue;

public class MaximumDepthBinaryTree {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    // Recursive solution 
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        return 1 + Math.max(leftDepth, rightDepth);
    }

    // Iterative solution using BFS 
    // Counts levels by processing one full level at a time. Useful 
    // when the tree might be deep and recursion could overflow.
    public static int maxDepthIterative(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;

        while (!queue.isEmpty()) {
            // Snapshot the level size before processing — children added
            // during this loop belong to the next level, not this one.
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            depth++;
        }

        return depth;
    }
}

9. Test the Code

// Standard tree
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
System.out.println(maxDepth(root));  // 3

// Empty tree
System.out.println(maxDepth(null));  // 0

// Single node
System.out.println(maxDepth(new TreeNode(1)));  // 1

// Left-skewed tree (depth equals chain length)
TreeNode skewed = new TreeNode(1);
skewed.left = new TreeNode(2);
skewed.left.left = new TreeNode(3);
skewed.left.left.left = new TreeNode(4);
System.out.println(maxDepth(skewed));  // 4

// Unbalanced — left and right depths differ
TreeNode unbalanced = new TreeNode(1);
unbalanced.left = new TreeNode(2);
unbalanced.right = new TreeNode(3);
unbalanced.left.left = new TreeNode(4);
unbalanced.left.left.left = new TreeNode(5);
System.out.println(maxDepth(unbalanced));  // 4 (left side is deeper)

These hit the meaningful cases: a normal tree, the empty case, a single node, a fully skewed chain, and an unbalanced tree that proves the max is actually selecting the deeper side.

10. Key Lessons

• When a problem definition is itself recursive ("depth is one more than the max of its subtrees' depths"), the algorithm is usually a direct translation of the definition into code. Don't overthink it — write down what the problem says.

• The base case is where the units of measurement get fixed. If you're counting nodes, null → 0 makes leaves count as 1. If you were counting edges, the base case would be different. Pick the base case to match the problem's definition.

• Postorder-style tree recursion (compute children's answers first, then combine at the current node) is the standard pattern for problems where each node's answer depends on its children's answers. Use it for depth, diameter, balance checks, and sum-of-subtree problems.

• Recursion's space complexity is O(h), which is great for balanced trees but bad for skewed ones. If you suspect adversarial inputs, the iterative BFS version trades stack for heap memory and avoids the overflow risk.

• "Simple" problems still test precision. The candidate who confidently nails the base case and explains why the recursion is correct in one breath is more impressive than one who writes complicated code to solve a one-line problem.

The thing that makes Maximum Depth click isn't difficulty — it's the recognition that the problem statement is already the algorithm. The recurrence isn't something you discover; it's something you transcribe. Once you can read a recursive problem definition and immediately see the recurrence inside it, every other tree-measurement problem starts to feel routine.

Good Luck and Happy Coding!