47.Maximum Depth of Binary Tree

EasyBlind 75Trees · 2/15

Problem

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

An empty tree has depth 0; a tree with only a root has depth 1.

Examples

Input:  root = [3,9,20,null,null,15,7]
Output: 3
Explanation: The longest root-to-leaf paths are 3 -> 20 -> 15 and 3 -> 20 -> 7, each with 3 nodes.

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

Input:  root = []
Output: 0

Constraints

The number of nodes in the tree is in the range [0, 10^4].
-100 <= Node.val <= 100

💡 Key Insight

Depth satisfies a simple recurrence: depth(node) = 1 + max(depth(node.left), depth(node.right)), with depth(null) = 0. Equivalently, it is the number of levels a BFS walks through. Either way, each node is touched once, giving O(n).

Iterative DFS with a Stack

TimeO(n)SpaceO(h)

Intuition

Simulate the recursion explicitly: push (node, depthOfNode) pairs onto a stack. Every time a node is popped, its depth is a candidate for the answer, and its children are pushed with depth + 1.

Algorithm

If root is null, return 0.
Push (root, 1) onto two parallel stacks (nodes and depths).
While the stack is not empty, pop (node, d), update max = max(max, d), and push non-null children with d + 1.
Return max.

Visualization

stack: [(3,1)]                max = 1
pop (3,1)  push (9,2),(20,2)  max = 1
pop (20,2) push (15,3),(7,3)  max = 2
pop (7,3)                     max = 3
pop (15,3)                    max = 3
pop (9,2)                     max = 3   -> answer 3

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> nodes = new ArrayDeque<>();
        Deque<Integer> depths = new ArrayDeque<>();
        nodes.push(root);
        depths.push(1);
        int max = 0;
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            int depth = depths.pop();
            max = Math.max(max, depth);
            if (node.left != null) {
                nodes.push(node.left);
                depths.push(depth + 1);
            }
            if (node.right != null) {
                nodes.push(node.right);
                depths.push(depth + 1);
            }
        }
        return max;
    }
}

Complexity

Time: O(n) — every node is pushed and popped once.
Space: O(h) — the stack holds pending siblings along the current path; O(n) for a skewed tree.

BFS Level Counting

TimeO(n)SpaceO(w)

Intuition

BFS processes the tree one level at a time. If we drain the queue level by level, the number of levels processed is exactly the maximum depth.

Algorithm

If root is null, return 0.
Enqueue root, set levels = 0.
While the queue is not empty:
- Let size = queue.size() (nodes on the current level).
- Poll size nodes, enqueuing their children.
- Increment levels.
Return levels.

Visualization

level 1: [3]        -> enqueue 9, 20
level 2: [9, 20]    -> enqueue 15, 7
level 3: [15, 7]    -> nothing to enqueue
queue empty -> levels = 3

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int levels = 0;
        while (!queue.isEmpty()) {
            int size = queue.size(); // nodes on this level
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            levels++;
        }
        return levels;
    }
}

Complexity

Time: O(n) — each node is enqueued once.
Space: O(w) — the widest level, up to about n/2 nodes in a complete tree.

Recursive DFSOptimal

TimeO(n)SpaceO(h)

Intuition

A tree's depth is one (for the current node) plus the depth of its deeper subtree. Recursion expresses this in one line, and the base case null -> 0 handles leaves and empty trees.

Algorithm

If root is null, return 0.
Return 1 + max(maxDepth(root.left), maxDepth(root.right)).

Dry Run

flowchart TD
    N3["3<br/>1 + max(1, 2) = 3"] --> N9["9<br/>1 + max(0, 0) = 1"]
    N3 --> N20["20<br/>1 + max(1, 1) = 2"]
    N20 --> N15["15<br/>returns 1"]
    N20 --> N7["7<br/>returns 1"]

Values flow upward: leaves return 1, node 20 returns 2, and the root returns 3.

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0; // empty subtree contributes no levels
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

Complexity

Time: O(n) — each node is visited once.
Space: O(h) — recursion depth; O(log n) for a balanced tree, O(n) for a skewed one.

Complexity Comparison

Approach	Time	Space
Iterative DFS with a Stack	O(n)	O(h)
BFS Level Counting	O(n)	O(w)
Recursive DFS	O(n)	O(h)

Common Pitfalls

Counting edges instead of nodes — this problem counts nodes, so a single-node tree has depth 1, not 0.
Returning 1 for a null node, which adds a phantom level everywhere.
In BFS, reading queue.size() inside the loop condition instead of snapshotting it — the size changes as children are enqueued, mixing levels.
With 10^4 nodes in a skewed tree, recursion depth reaches 10^4; it is fine on LeetCode, but iterative versions avoid stack overflow on much larger inputs.