Problem 16.1 · Binary TreesEasy

Maximum Depth of Binary Tree

What it teaches: The simplest post-order recursion: depth = 1 + the deeper subtree.

Practise it on judges as “Maximum Depth of Binary Tree”.

The problem

Return the maximum depth of a binary tree: the number of nodes on the longest path from the root to a leaf.

Example 1

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

Example 2

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

Constraints

0 ≤ nodes ≤ 10⁴

Pattern clues in the wording

→ Answer for a node depends on both subtrees

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int maxDepth(TreeNode root) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	root = [3,9,20,null,null,15,7]	3
2	root = [1,null,2]	2
3	root = []	0

From slow to fast

Approaches

1. Recursive DFS · O(n)2. BFS counting levels · O(n)

Recursive DFS

Time O(n) Space O(h) for the recursion

Return 0 for null; otherwise 1 + max of the children's depths.

▶ Dry run: Depths bubbling uproot = [3, 9, 20, null, null, 15, 7]

Step 1/49 is a leaf: depth 1.

Approach 1

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

Verdict: Every node visited once.

BFS counting levels

Time O(n) Space O(width)

Process level by level and count the levels.

Approach 2

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        int depth = 0;
        while (!q.isEmpty()) {
            depth++;
            for (int size = q.size(); size > 0; size--) {
                TreeNode n = q.poll();
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
        }
        return depth;
    }
}

Verdict: Avoids deep recursion on skewed trees.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty tree → 0
Single node → 1
Skewed tree (a linked list)

Mistakes people make

Returning 1 for null.

Interview

Follow-up questions

What about the minimum depth?

Command Palette