Loading…

easyTreesLC #104Frequently asked

Maximum Depth of Binary Tree

Q: How do you solve Maximum Depth of Binary Tree using the Recursive DFS — 1 + max(left, right) (Optimal) approach?

When to use it: Start here. It's a one-liner and the textbook example of postorder bottom-up aggregation. Depth has a naturally recursive definition: the depth of a tree is one more than the depth of its deeper subtree. That single sentence is the whole algorithm. **Base case.** A null node represents an empty subtree, which has depth 0. Returning 0 here is what makes a leaf node (whose two children are null) report `1 + max(0, 0) = 1` — exactly the node-counting definition. **Recursive case.** For a real node, ask both children for their depths, take the larger (the longest path goes through whichever subtree is deeper), and add 1 to account for the current node sitting above them. The `max` is essential: a node's depth is dictated by its *deepest* descendant, not the average or the sum. **Why this is postorder.** A node cannot compute its own depth until *both* children have reported theirs — the work happens on the way back *up* the recursion. That's the definition of postorder / bottom-up processing, and recognizing it is the transferable skill: Balanced Tree, Diameter of a Binary Tree, and Maximum Path Sum all use this same 'children return a value, parent combines it' structure. **Nodes vs edges.** LeetCode counts depth in nodes, so a single node is depth 1 and an empty tree is depth 0. Some textbooks define height in edges (single node = 0). The code is the same; just confirm the convention so you're not off by one. Time complexity: O(n). Space complexity: O(h).

Q: How do you solve Maximum Depth of Binary Tree using the Iterative BFS — Count the Levels approach?

When to use it: Offer as the iterative version, especially if the interviewer worries about recursion depth or pivots toward minimum depth (where BFS shines). Maximum depth is just the number of levels, so a level-order BFS that counts levels answers it directly without recursion. **The level-drain trick.** Seed a queue with the root and a depth counter at 0. Each outer-loop iteration represents one level: record the current queue size (that's how many nodes are on this level), then dequeue *exactly that many* nodes, enqueuing each one's children. After draining the level, increment the depth. When the queue is empty, every level has been counted and the depth is the answer. **Why record the size up front.** The queue grows as you enqueue children, so you must snapshot `levelSize` before the inner loop — otherwise you'd bleed into the next level and miscount. This 'capture the size, then loop exactly that many times' idiom is the universal BFS-by-level pattern, reused in Level Order Traversal, Right Side View, and Zigzag Traversal. **When BFS beats DFS.** For *maximum* depth they're equivalent. But for *minimum* depth (LeetCode 111), BFS is strictly better: the first leaf you encounter is on the shallowest level, so you can return immediately instead of exploring the whole tree. Mentioning that distinction shows you understand *why* you'd pick one traversal over the other, not just that both exist. Time complexity: O(n). Space complexity: O(w).

LCPractice

Trees & BST · 4 of 41 · 7 min

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

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

In plain English

Find the length (in nodes) of the longest root-to-leaf path. Equivalently, the tree's height + 1 if you count height in edges. We don't need the path itself, just its length, so a single integer flows up the recursion.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: 3
Note: Longest path is 3 → 20 → 15 (or 3 → 20 → 7), three nodes deep.

Example 2

Input: root = [1,null,2]
Output: 2
Note: Path 1 → 2 has two nodes. The missing left child contributes depth 0.

Example 3

Input: root = []
Output: 0
Note: Empty tree has depth 0 — the base case.

Constraints

The number of nodes is in the range [0, 10⁴]
-100 ≤ Node.val ≤ 100
An empty tree has depth 0

Clarifying questions4First question: Is depth measured in nodes or edges?Explore questions

Q1.Is depth measured in nodes or edges?
LeetCode 104 counts nodes — a single node has depth 1. If the definition were edges, a single node would be depth 0. Confirm which, since it shifts every answer by one.
Q2.Can the tree be empty?
Yes — node count can be 0, and the depth of an empty tree is 0. That's the recursion's base case.
Q3.Could the tree be deep enough to overflow recursion?
With up to 10⁴ nodes a skewed tree is 10⁴ deep — usually fine in Java/Python, but mention the BFS alternative if call-stack limits are a concern.
Q4.Do you want max or min depth?
Max here. Min depth (LeetCode 111) is subtly different — BFS short-circuits at the first leaf, and DFS must avoid counting through a missing child.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The maximum depth is the number of nodes on the longest root-to-leaf path. The one-line recursive answer: depth = 1 + max(depth(left), depth(right)), with an empty tree contributing 0. That's postorder DFS — a node's answer depends on its children. The iterative alternative is a BFS that counts how many levels the queue processes. Both are O(n) time; DFS is O(h) space, BFS is O(w) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize tree height as a postorder aggregation — children compute first, parent combines — and can also express it as a level-counting BFS.

Where candidates slip

Returning 0 for a single node (confusing node-count depth with edge-count height), or using min instead of max, or counting per node instead of per level in the BFS.

How to stand out

State that this is postorder/bottom-up, contrast depth-as-nodes vs height-as-edges, and offer the BFS level count as the iterative variant — then note this is the engine behind Balanced Tree and Diameter.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive DFS — 1 + max(left, right) (Optimal)Optimal	`O(n)`	`O(h)`	Start here. It's a one-liner and the textbook example of postorder bottom-up aggregation.	Read
2	Iterative BFS — Count the Levels	`O(n)`	`O(w)`	Offer as the iterative version, especially if the interviewer worries about recursion depth or pivots toward minimum depth (where BFS shines).	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewLongest root-to-leaf path length?Recursion or explicit container?RecursionExplicitExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Recursive DFS — 1 + max(left, right) (Optimal)

TimeO(n)SpaceO(h)

Start here. It's a one-liner and the textbook example of postorder bottom-up aggregation.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you somehow knew the depth of the left subtree and the depth of the right subtree, how would you compute the depth of the whole tree?

2Hint 2Explore hint

The tree's depth is 1 (for the root) plus the deeper of its two subtrees. That's a recursive definition — what's the base case?

3Hint 3Explore hint

Base case: a null node has depth 0. Recursive case: return 1 + max(depth(left), depth(right)).

A · Core idea

Depth has a naturally recursive definition: the depth of a tree is one more than the depth of its deeper subtree. That single sentence is the whole algorithm.

Base case. A null node represents an empty subtree, which has depth 0. Returning 0 here is what makes a leaf node (whose two children are null) report 1 + max(0, 0) = 1 — exactly the node-counting definition.

Recursive case. For a real node, ask both children for their depths, take the larger (the longest path goes through whichever subtree is deeper), and add 1 to account for the current node sitting above them. The max is essential: a node's depth is dictated by its deepest descendant, not the average or the sum.

Why this is postorder. A node cannot compute its own depth until both children have reported theirs — the work happens on the way back up the recursion. That's the definition of postorder / bottom-up processing, and recognizing it is the transferable skill: Balanced Tree, Diameter of a Binary Tree, and Maximum Path Sum all use this same 'children return a value, parent combines it' structure.

Nodes vs edges. LeetCode counts depth in nodes, so a single node is depth 1 and an empty tree is depth 0. Some textbooks define height in edges (single node = 0). The code is the same; just confirm the convention so you're not off by one.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [3,9,20,null,null,15,7]

Depths bubbling up [3,9,20,null,null,15,7]

How to read it:Leaves return 1; node 20 returns 2; root 3 returns 1 + max(1,2) = 3.

Rendering diagram…

Final result3

C · Code with teaching comments

solution.javaJava

Recursive DFS — 1 + max(left, right) (Optimal) — optimal

3 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public int maxDepth(TreeNode root) {
10
    if (root == null) return 0;                         // empty subtree
11
    int leftDepth = maxDepth(root.left);                // children report first
12
    int rightDepth = maxDepth(root.right);
13
    return 1 + Math.max(leftDepth, rightDepth);         // parent combines
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

The recursion returns up the tree, not down. Each node waits for its children's answers, then folds them with 1 + max(...). When you see 'a node's result depends on its subtrees', reach for this postorder shape — it's the most reused tree pattern in interviews.

ComplexityO(n) time, O(h) space — Every node is visited exactly once and does O(1) work (a max and an add) → O(n) time. The recursion depth equals the tree height h → O(h) space: O(log n) for a balanced tree, O(n) for a skewed one.

E · Edge cases and pitfalls6root = [] — Base case returns 0 immediately.Explore edge cases

Edge cases handled

root = []Base case returns 0 immediately.
root = [1]1 + max(0,0) = 1 — a single node has depth 1 under the node-counting definition.
Left-skewed chain of 4 nodesEach level adds 1 down the left spine → returns 4; recursion depth is also 4 (O(n)).

Pitfalls

Returning 0 for a single node — that's the edge-count height, not the node-count depth LeetCode wants.
Using min instead of max — gives the shortest path, not the longest.
Adding the two child depths instead of taking the max — that's not a path length at all.

03.2

Approach 2 of 2

Iterative BFS — Count the Levels

TimeO(n)SpaceO(w)

Offer as the iterative version, especially if the interviewer worries about recursion depth or pivots toward minimum depth (where BFS shines).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Depth equals the number of levels in the tree. How would you process a tree one full level at a time?

2Hint 2Explore hint

Use a queue. At the start of each outer loop, the queue holds exactly one level; drain all of them while enqueuing their children.

3Hint 3Explore hint

Increment a depth counter once per level (per drain), not once per node. When the queue empties, the counter is the depth.

A · Core idea

Maximum depth is just the number of levels, so a level-order BFS that counts levels answers it directly without recursion.

The level-drain trick. Seed a queue with the root and a depth counter at 0. Each outer-loop iteration represents one level: record the current queue size (that's how many nodes are on this level), then dequeue exactly that many nodes, enqueuing each one's children. After draining the level, increment the depth. When the queue is empty, every level has been counted and the depth is the answer.

Why record the size up front. The queue grows as you enqueue children, so you must snapshot levelSize before the inner loop — otherwise you'd bleed into the next level and miscount. This 'capture the size, then loop exactly that many times' idiom is the universal BFS-by-level pattern, reused in Level Order Traversal, Right Side View, and Zigzag Traversal.

When BFS beats DFS. For maximum depth they're equivalent. But for minimum depth (LeetCode 111), BFS is strictly better: the first leaf you encounter is on the shallowest level, so you can return immediately instead of exploring the whole tree. Mentioning that distinction shows you understand why you'd pick one traversal over the other, not just that both exist.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [3,9,20,null,null,15,7]

level 1

drain [3], enqueue 9,20

Statedepth=1, queue=[9,20]

Final result3

C · Code with teaching comments

Reference implementation previewpublic int maxDepth(TreeNode root) { if (root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0;Explore the full code

solution.javaJava

Iterative BFS — Count the Levels — reference

4 teaching notes

1
public int maxDepth(TreeNode root) {
2
    if (root == null) return 0;
3
    Queue<TreeNode> queue = new LinkedList<>();
4
    queue.offer(root);
5
    int depth = 0;
6
    while (!queue.isEmpty()) {
7
        int levelSize = queue.size();        // snapshot this level's count
8
        // Process exactly one level's worth of nodes.
9
        for (int i = 0; i < levelSize; i++) {
10
            TreeNode node = queue.poll();
11
            // Enqueue children for the next level; skip nulls.
12
            if (node.left != null) queue.offer(node.left);
13
            if (node.right != null) queue.offer(node.right);
14
        }
15
        depth++;                             // one full level processed
16
    }
17
    return depth;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n) timeO(w) spaceOpen the invariant and proofExplore the proof

The 'snapshot the queue size, then dequeue exactly that many' move is the heart of every level-by-level BFS. Counting levels with it gives depth; collecting the popped values per level gives Level Order Traversal — same skeleton, different payload.

ComplexityO(n) time, O(w) space — Each node is enqueued and dequeued once → O(n) time. The queue holds at most one level at a time, so its size is bounded by the tree's maximum width w → O(w) space (up to O(n) for the widest level of a balanced tree).

E · Edge cases and pitfalls6root = [] — Guard returns 0 before the queue starts.Explore edge cases

Edge cases handled

root = []Guard returns 0 before the queue starts.
root = [1]One level drained → depth 1.
Perfect tree of height hQueue peaks at the last level (~n/2 nodes) → O(n) space worst case for BFS.

Pitfalls

Reading queue.size() inside the inner loop instead of snapshotting it — bleeds levels together.
Incrementing depth per node instead of per level — wildly overcounts.
Enqueuing null children — can cause a null dereference when you later poll them.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

min instead of max

Maximum depth follows the LONGEST root-to-leaf path. Using min returns the shortest path length, which is a different problem (and even that needs a one-child guard).

Explore the code comparison

Don't write this

def maxDepth(self, root):
    if not root:
        return 0
    return 1 + min(self.maxDepth(root.left), self.maxDepth(root.right))

Write this instead

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

Counting per node instead of per level in BFS

Incrementing the depth on every dequeue counts nodes, not levels. You must snapshot the level size and bump depth once per drained level.

Explore the code comparison

Don't write this

while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    if (node.left != null) queue.offer(node.left);
    if (node.right != null) queue.offer(node.right);
    depth++;   // counts NODES, not levels
}

Write this instead

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++;   // once per level
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Postorder DFS aggregation (1 + max of children) — or BFS level counting

Code pattern to memorize

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

Rules to remember

1Empty tree → depth 0; a single node → depth 1. Anchor on these two base values.
2It's postorder: a node can't know its depth until both children report theirs — children before parent.
3Take the max of the two child depths, then +1 for the current node.
4BFS alternative: increment a counter once per level (drain the whole queue before counting the next).
5Depth = node count on the longest path here (LeetCode counts nodes, not edges).

Use this pattern when

You need the height/depth of a tree or longest root-to-leaf path
Any value where a node's answer is built from its children's answers (bottom-up)
A building block for Balanced Tree, Diameter, and Max Path Sum

Choose another pattern when

You need the MINIMUM depth → BFS short-circuits at the first leaf; DFS must guard one-child nodes
You need per-level node lists → that's Level Order Traversal, not just a count
You need the path itself, not its length → carry the path, not just the count

Interview takeaway

Maximum Depth is the cleanest example of bottom-up (postorder) aggregation: each node returns 1 plus the larger of its children's returns. Internalize this shape — Balanced Tree, Diameter, and Max Path Sum are all this same recursion with a tiny twist.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPostorder (bottom-up) aggregation: children return a value, the parent combines them with 1 + max(...). This is the most reused tree recursion — Balanced Tree, Diameter, and Max Path Sum are all the same shape with extra bookkeeping. The BFS level-count is the iterative twin and the gateway to all level-order problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Minimum Depth of Binary Tree
Coming soon
BFS returns at the first leaf; in DFS, a node with one missing child must take the existing child's depth, not min with 0.
Balanced Binary Tree
Same height recursion, but also check |leftHeight - rightHeight| ≤ 1 at every node.
Diameter of Binary Tree
Track leftDepth + rightDepth at each node while the recursion returns the height upward.
Binary Tree Level Order Traversal
Same level-drain BFS, but collect the popped values per level instead of just counting.

Same pattern

←

Invert Binary Tree

Continue · Next problem

Balanced Binary Tree

easyTreesLC #104Frequently asked

Maximum Depth of Binary Tree

LCPractice

Trees & BST · 4 of 41 · 7 min

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

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

In plain English

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: 3
Note: Longest path is 3 → 20 → 15 (or 3 → 20 → 7), three nodes deep.

Example 2

Input: root = [1,null,2]
Output: 2
Note: Path 1 → 2 has two nodes. The missing left child contributes depth 0.

Example 3

Input: root = []
Output: 0
Note: Empty tree has depth 0 — the base case.

Constraints

The number of nodes is in the range [0, 10⁴]
-100 ≤ Node.val ≤ 100
An empty tree has depth 0

Clarifying questions4First question: Is depth measured in nodes or edges?Explore questions

Q1.Is depth measured in nodes or edges?
LeetCode 104 counts nodes — a single node has depth 1. If the definition were edges, a single node would be depth 0. Confirm which, since it shifts every answer by one.
Q2.Can the tree be empty?
Yes — node count can be 0, and the depth of an empty tree is 0. That's the recursion's base case.
Q3.Could the tree be deep enough to overflow recursion?
With up to 10⁴ nodes a skewed tree is 10⁴ deep — usually fine in Java/Python, but mention the BFS alternative if call-stack limits are a concern.
Q4.Do you want max or min depth?
Max here. Min depth (LeetCode 111) is subtly different — BFS short-circuits at the first leaf, and DFS must avoid counting through a missing child.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize tree height as a postorder aggregation — children compute first, parent combines — and can also express it as a level-counting BFS.

Where candidates slip

Returning 0 for a single node (confusing node-count depth with edge-count height), or using min instead of max, or counting per node instead of per level in the BFS.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive DFS — 1 + max(left, right) (Optimal)Optimal	`O(n)`	`O(h)`	Start here. It's a one-liner and the textbook example of postorder bottom-up aggregation.	Read
2	Iterative BFS — Count the Levels	`O(n)`	`O(w)`	Offer as the iterative version, especially if the interviewer worries about recursion depth or pivots toward minimum depth (where BFS shines).	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Recursive DFS — 1 + max(left, right) (Optimal)

TimeO(n)SpaceO(h)

Start here. It's a one-liner and the textbook example of postorder bottom-up aggregation.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you somehow knew the depth of the left subtree and the depth of the right subtree, how would you compute the depth of the whole tree?

2Hint 2Explore hint

The tree's depth is 1 (for the root) plus the deeper of its two subtrees. That's a recursive definition — what's the base case?

3Hint 3Explore hint

Base case: a null node has depth 0. Recursive case: return 1 + max(depth(left), depth(right)).

A · Core idea

Depth has a naturally recursive definition: the depth of a tree is one more than the depth of its deeper subtree. That single sentence is the whole algorithm.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [3,9,20,null,null,15,7]

Depths bubbling up [3,9,20,null,null,15,7]

How to read it:Leaves return 1; node 20 returns 2; root 3 returns 1 + max(1,2) = 3.

Rendering diagram…

Final result3

C · Code with teaching comments

solution.javaJava

Recursive DFS — 1 + max(left, right) (Optimal) — optimal

3 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public int maxDepth(TreeNode root) {
10
    if (root == null) return 0;                         // empty subtree
11
    int leftDepth = maxDepth(root.left);                // children report first
12
    int rightDepth = maxDepth(root.right);
13
    return 1 + Math.max(leftDepth, rightDepth);         // parent combines
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6root = [] — Base case returns 0 immediately.Explore edge cases

Edge cases handled

root = []Base case returns 0 immediately.
root = [1]1 + max(0,0) = 1 — a single node has depth 1 under the node-counting definition.
Left-skewed chain of 4 nodesEach level adds 1 down the left spine → returns 4; recursion depth is also 4 (O(n)).

Pitfalls

Returning 0 for a single node — that's the edge-count height, not the node-count depth LeetCode wants.
Using min instead of max — gives the shortest path, not the longest.
Adding the two child depths instead of taking the max — that's not a path length at all.

03.2

Approach 2 of 2

Iterative BFS — Count the Levels

TimeO(n)SpaceO(w)

Offer as the iterative version, especially if the interviewer worries about recursion depth or pivots toward minimum depth (where BFS shines).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Depth equals the number of levels in the tree. How would you process a tree one full level at a time?

2Hint 2Explore hint

Use a queue. At the start of each outer loop, the queue holds exactly one level; drain all of them while enqueuing their children.

3Hint 3Explore hint

Increment a depth counter once per level (per drain), not once per node. When the queue empties, the counter is the depth.

A · Core idea

Maximum depth is just the number of levels, so a level-order BFS that counts levels answers it directly without recursion.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [3,9,20,null,null,15,7]

level 1

drain [3], enqueue 9,20

Statedepth=1, queue=[9,20]

Final result3

C · Code with teaching comments

Reference implementation previewpublic int maxDepth(TreeNode root) { if (root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0;Explore the full code

solution.javaJava

Iterative BFS — Count the Levels — reference

4 teaching notes

1
public int maxDepth(TreeNode root) {
2
    if (root == null) return 0;
3
    Queue<TreeNode> queue = new LinkedList<>();
4
    queue.offer(root);
5
    int depth = 0;
6
    while (!queue.isEmpty()) {
7
        int levelSize = queue.size();        // snapshot this level's count
8
        // Process exactly one level's worth of nodes.
9
        for (int i = 0; i < levelSize; i++) {
10
            TreeNode node = queue.poll();
11
            // Enqueue children for the next level; skip nulls.
12
            if (node.left != null) queue.offer(node.left);
13
            if (node.right != null) queue.offer(node.right);
14
        }
15
        depth++;                             // one full level processed
16
    }
17
    return depth;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n) timeO(w) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6root = [] — Guard returns 0 before the queue starts.Explore edge cases

Edge cases handled

root = []Guard returns 0 before the queue starts.
root = [1]One level drained → depth 1.
Perfect tree of height hQueue peaks at the last level (~n/2 nodes) → O(n) space worst case for BFS.

Pitfalls

Reading queue.size() inside the inner loop instead of snapshotting it — bleeds levels together.
Incrementing depth per node instead of per level — wildly overcounts.
Enqueuing null children — can cause a null dereference when you later poll them.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

min instead of max

Maximum depth follows the LONGEST root-to-leaf path. Using min returns the shortest path length, which is a different problem (and even that needs a one-child guard).

Explore the code comparison

Don't write this

def maxDepth(self, root):
    if not root:
        return 0
    return 1 + min(self.maxDepth(root.left), self.maxDepth(root.right))

Write this instead

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

Counting per node instead of per level in BFS

Incrementing the depth on every dequeue counts nodes, not levels. You must snapshot the level size and bump depth once per drained level.

Explore the code comparison

Don't write this

while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    if (node.left != null) queue.offer(node.left);
    if (node.right != null) queue.offer(node.right);
    depth++;   // counts NODES, not levels
}

Write this instead

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++;   // once per level
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Postorder DFS aggregation (1 + max of children) — or BFS level counting

Code pattern to memorize

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

Rules to remember

1Empty tree → depth 0; a single node → depth 1. Anchor on these two base values.
2It's postorder: a node can't know its depth until both children report theirs — children before parent.
3Take the max of the two child depths, then +1 for the current node.
4BFS alternative: increment a counter once per level (drain the whole queue before counting the next).
5Depth = node count on the longest path here (LeetCode counts nodes, not edges).

Use this pattern when

You need the height/depth of a tree or longest root-to-leaf path
Any value where a node's answer is built from its children's answers (bottom-up)
A building block for Balanced Tree, Diameter, and Max Path Sum

Choose another pattern when

You need the MINIMUM depth → BFS short-circuits at the first leaf; DFS must guard one-child nodes
You need per-level node lists → that's Level Order Traversal, not just a count
You need the path itself, not its length → carry the path, not just the count

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Minimum Depth of Binary Tree
Coming soon
BFS returns at the first leaf; in DFS, a node with one missing child must take the existing child's depth, not min with 0.
Balanced Binary Tree
Same height recursion, but also check |leftHeight - rightHeight| ≤ 1 at every node.
Diameter of Binary Tree
Track leftDepth + rightDepth at each node while the recursion returns the height upward.
Binary Tree Level Order Traversal
Same level-drain BFS, but collect the popped values per level instead of just counting.

Same pattern

←

Invert Binary Tree

Continue · Next problem

Balanced Binary Tree