Difficulty: EasyTrees

Maximum Depth of Binary Tree

Problem in Plain English

Given the root of a binary tree, return the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0.

Problem Statement

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

The maximum depth is the number of nodes along the longest downward path from the root to any leaf. An empty tree has depth 0, and a single node has depth 1.

Constraints

$0 \le n \le 10^4$ , where $n$ is the number of nodes.
$-100 \le \text{Node.val} \le 100$ .

Examples

Example 1

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

The path 3 to 20 to 15 holds 3 nodes, which beats the 2-node path through 9.

Example 2

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

The missing left child does not stop the path through the right child: 1 to 2 contains two nodes. A minimum of the child depths would incorrectly discard this path.

Example 3

Input: root = []
Output: 0

Empty edge case: there is no root and no root-to-leaf path, so zero nodes contribute to the depth.

Example 4

Input: root = [0,-1,-1,null,null,-1,null,-1]
Output: 4

Duplicate negative values denote distinct nodes. The right subtree continues down a left-child chain, giving the four-node path with values 0, -1, -1, -1. Values and signs do not determine depth.

Intuition

Depth counts nodes on one downward path, not edges or values. In Example 1, the path from 3 through 20 to 15 has three nodes, while the path to 9 has two. Count nonempty horizontal levels, or compute each child subtree depth and add one to the larger answer. An empty child contributes zero, making a leaf contribute one; taking a maximum chooses one path rather than combining both branches.

Approaches

Level Count With BFS

Solution Details

Reveal Level Count With BFS: intuition, complexity, and code

Intuition

Count one unit of depth per nonempty breadth-first frontier. Each frontier contains exactly one level; its children form the next frontier. Example 1 has [3], then [9,20], then [15,7]. Two level arrays avoid recursion and repeated removal from the front of a JavaScript array.

Step-by-Step Logic

Return 0 for an empty root. Otherwise initialize level with the root and depth with 0; Example 1 starts at [3].
For each nonempty frontier, increment depth and allocate an empty next frontier. Processing root 3 raises depth to 1 and collects [9,20].
Append existing children into the next frontier while iterating only the current level, then replace the frontier. Processing [9,20] at depth 2 collects [15,7].
Repeat until the next frontier is empty. Processing leaves 15 and 7 raises depth to 3 and collects no children, so return 3.

Why It Works

Initially the frontier contains only the root, exactly the first level. Assuming a frontier contains exactly all nodes in its level, each child is one edge deeper and each node in the next level has one parent in the current frontier. Collecting those children therefore creates precisely the next level. Incrementing depth once per nonempty frontier counts every level exactly once. The final nonempty level contains a deepest leaf, and its level number equals the number of nodes on the longest root-to-leaf path. The empty-root guard returns zero.

Dry Run

Level Count With BFS: variable states at each step
event	current frontier	node	next frontier	depth
initialize	`[3]`	none	not allocated	`0`
begin level	`[3]`	none	`[]`	`0 → 1`
append children	`[3]`	`3`	`[9,20]`	`1`
replace and begin	`[9,20]`	none	`[]`	`1 → 2`
append children	`[9,20]`	`9`	`[]`	`2`
append children	`[9,20]`	`20`	`[15,7]`	`2`
replace and begin	`[15,7]`	none	`[]`	`2 → 3`
append children	`[15,7]`	`15`	`[]`	`3`
append children	`[15,7]`	`7`	`[]`	`3`
replace; stop	`[]`	none	`[]`	return `3`

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(w)

Each of n nodes is processed once and each child reference appended once. Maximum level width w bounds each frontier; current and next arrays coexist, so peak auxiliary storage holds at most two levels and O(w) references, O(n) in the worst case. Across the traversal O(n) references and O(h) arrays are allocated cumulatively, where h is depth; obsolete arrays become reclaimable. No nodes are copied or changed, and the scalar output uses O(1) space.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3
4class TreeNode {5    int val;6    TreeNode left, right;7    TreeNode(int val) { this.val = val; }8}9
10class Solution {11    public int maxDepth(TreeNode root) {12        if (root == null) return 0;13        List<TreeNode> level = new ArrayList<>();14        level.add(root);15        int depth = 0;16        while (!level.isEmpty()) {17            depth++;18            List<TreeNode> next = new ArrayList<>();19            // Separate frontiers keep children out of their parents' level.20            for (TreeNode node : level) {21                if (node.left != null) next.add(node.left);22                if (node.right != null) next.add(node.right);23            }24            level = next;25        }26        return depth;27    }28}

Hints

Hint 1

Does changing a node value change the number of nodes on a path? Focus on child links.

Hint 2

An empty subtree contributes zero. What should a leaf return?

Hint 3

A downward path chooses one child: take the larger child depth and add the current node.

Hint 4

Alternatively, count nonempty breadth-first frontiers, keeping children separate from the current level.

Edge Cases

An empty tree returns 0; a singleton returns 1, including zero or negative values.
Left-only, right-only, and alternating chains have depth n; at 10,000 nodes BFS remains independent of recursive stack capacity.
A missing child contributes zero without stopping the existing child path.
A complete tree has modest depth but a wide BFS frontier; recursion stores only one root-to-leaf path.
Duplicate values do not identify nodes. Neither approach changes values or child references.

Common Mistakes and Interview Tips

Counting edges instead of nodes: use zero for null and add one for every nonempty node.
Adding both child depths combines separate paths; taking their minimum discards longer paths, especially when one child is missing.
Appending children to the array being iterated mixes levels. Collect them in a separate next frontier.
Repeated JavaScript shift() may move remaining array entries and make wide-tree traversal quadratic.
Assuming default stacks support all legal chains: Java and JavaScript can overflow at 10,000 nodes. Provision stack capacity or choose BFS. Python recursion limits are process-wide and should not be changed concurrently by other threads.
Retaining a global depth counter across invocations gives stale answers; keep traversal state local.

Key Takeaway

Height is a post-order summary: empty contributes zero, and each parent adds itself to the larger child answer. Breadth-first level counting computes the same quantity outward from the root. Choose between width-dependent frontier storage and height-dependent recursive storage according to tree shape and runtime stack capacity.