Minimum Depth of Binary Tree

📋

Problem

Imagine you want to find the shortest path to safety in a maze represented as a binary tree, where each node is a room and the exit is a leaf node. Finding the minimum depth is like finding the quickest escape route.

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf is a node with no children.

The number of nodes in the tree is in the range [1, 10^5]Node values can be any integerThe tree is not necessarily balanced

Edge cases: Single node tree → minimum depth is 1Tree where root has only one child → minimum depth is depth of that child subtreeTree with multiple leaves at different depths → minimum depth is the smallest among them

</>

IDE

def minDepth(root: Optional[TreeNode]) -> int:public int minDepth(TreeNode root)int minDepth(TreeNode* root)function minDepth(root)

def minDepth(root):
    # Write your solution here
    pass

class Solution {
    public int minDepth(TreeNode root) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int minDepth(TreeNode* root) {
    // Write your solution here
    return 0;
}

function minDepth(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Treating any node with a child as a leaf, causing premature stopping at root or first child.✅ Check that both left and right children are null before considering a node a leaf.

Wrong: 0Not handling empty tree input correctly, returning 0 only if root is null but missing that root can be null.✅ Add base case: if root is null, return 0 immediately.

Wrong: n (total nodes)Always returning maximum depth or height instead of minimum depth, ignoring early stopping at first leaf.✅ Use BFS to stop at first leaf node encountered and return that depth.

Wrong: Off-by-one errors (e.g., returning depth-1)Incorrect initialization or increment of depth counter during traversal.✅ Initialize depth as 1 at root and increment correctly per level.

Wrong: Timeout or no outputUsing exponential recursion without pruning or BFS, causing TLE on large inputs.✅ Implement BFS or optimized DFS with pruning to achieve O(n) time complexity.

✓

Test Cases

Make sure your solution handles empty and single node trees correctly before moving on.

Review leaf node definitions and avoid greedy traps to handle corner cases.

Optimize your solution to linear time complexity to handle large inputs efficiently.

t1_01basic

Input{"root":[3,9,20,null,null,15,7]}

Expected2

⏱ Performance - must finish in 2000ms

The shortest path to a leaf is from 3 to 9, which has length 2.

💡 Think about traversing the tree level by level to find the first leaf.

💡 Use a BFS approach to stop at the first encountered leaf node.

💡 Return the depth at which you find the first leaf node during BFS.

Why it failed: Returned wrong depth; likely did not stop at the first leaf found in BFS. Fix by returning depth immediately upon encountering a leaf node.

✓ Correctly identified the minimum depth using BFS.

t1_02basic

Input{"root":[1,2,3,4,null,null,5]}

Expected3

⏱ Performance - must finish in 2000ms

Minimum depth is 3 via path 1->2->4, since 4 is the first leaf encountered.

💡 Check all children at each level before going deeper.

💡 Remember that a leaf is a node with no children, even if other branches are deeper.

💡 Return the depth when you find the first leaf node during BFS traversal.

Why it failed: Incorrect depth due to treating non-leaf nodes as leaves or not stopping early. Fix by verifying leaf condition and stopping BFS immediately.

✓ Correctly found minimum depth by stopping BFS at first leaf.

t2_01edge

Input{"root":null}

Expected0

⏱ Performance - must finish in 2000ms

Empty tree has minimum depth 0.

💡 Consider what the minimum depth should be if the tree is empty.

💡 Check if root is null before processing.

💡 Return 0 immediately if root is null.

Why it failed: Returned non-zero for empty tree; fix by adding base case: if root is null, return 0.

✓ Correctly handled empty tree with depth 0.

t2_02edge

Input{"root":[1]}

Expected1

⏱ Performance - must finish in 2000ms

Single node tree has minimum depth 1.

💡 Check if root has no children to identify leaf.

💡 If root is leaf, minimum depth is 1.

💡 Return 1 if root.left and root.right are null.

Why it failed: Returned depth > 1 for single node tree; fix by checking leaf condition at root and returning 1.

✓ Correctly returned 1 for single node tree.

t2_03edge

Input{"root":[1,2,null,3,null,4,null,5]}

Expected5

⏱ Performance - must finish in 2000ms

Tree is a chain of left children only; minimum depth equals number of nodes (5).

💡 Check that nodes with only one child are not considered leaves.

💡 Minimum depth is depth of the only child subtree plus one.

💡 Traverse down the single child path until leaf is found.

Why it failed: Incorrectly treated nodes with one child as leaves; fix by ensuring leaf check requires both children null.

✓ Correctly handled single-child chain with minimum depth 5.

t3_01corner

Input{"root":[1,2,3,4,5,null,null,null,null,6]}

Expected3

⏱ Performance - must finish in 2000ms

Minimum depth is 3 via path 1->2->5, leaf at node 5 (which has a child 6 but 5 itself is not leaf, so leaf is 6 at depth 4). Actually leaf is 4 at depth 3 (node 4 is leaf).

💡 Beware of greedy approaches that pick the first child without checking leaf status.

💡 Verify leaf nodes have no children before deciding minimum depth.

💡 Use BFS to find the first leaf node correctly, not just first child.

Why it failed: Greedy approach failed by returning depth of first child without checking if it's leaf. Fix by checking both children and only returning depth at leaf nodes.

✓ Correctly avoided greedy trap and found minimum depth 3.

t3_02corner

Input{"root":[1,null,2,null,3,null,4,null,5]}

Expected5

⏱ Performance - must finish in 2000ms

Right skewed tree with single path; minimum depth equals number of nodes (5).

💡 Check that nodes with only one child are not treated as leaves.

💡 Do not confuse 0/1 child nodes as leaves.

💡 Traverse down the only child path until leaf is found.

Why it failed: Mistakenly treated nodes with one child as leaves causing undercount. Fix by confirming leaf nodes have no children.

✓ Correctly handled skewed tree with minimum depth 5.

t3_03corner

Input{"root":[1,2,3,4,null,null,5,null,null,6]}

Expected3

⏱ Performance - must finish in 2000ms

Minimum depth is 3 via path 1->3->5, leaf at node 5.

💡 Avoid off-by-one errors in depth counting.

💡 Count root as depth 1, increment depth when moving down.

💡 Return depth as soon as leaf node is found.

Why it failed: Off-by-one error in depth counting caused wrong output. Fix by initializing depth at 1 for root and incrementing correctly per level.

✓ Correctly counted depth with no off-by-one errors.

t4_01performance

Input{"root":[1,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87,null,88,null,89,null,90,null,91,null,92,null,93,null,94,null,95,null,96,null,97,null,98,null,99,null,100],"right":null}

Expectednull

⏱ Performance - must finish in 2000ms

Deep left-skewed tree with n=100 nodes; BFS or DFS O(n) must complete within 2 seconds.

💡 Use BFS or DFS with pruning to achieve O(n) time.

💡 Avoid exponential recursion or repeated work.

💡 Use iterative BFS with queue to handle large input efficiently.

Why it failed: Solution timed out due to exponential or inefficient recursion. Fix by using BFS or optimized DFS with pruning to achieve O(n) time.

✓ Solution runs within time limits using O(n) BFS or DFS.

Practice

1. You are given a binary tree and asked to compute the average value of nodes on each level. Which algorithmic approach guarantees an optimal solution that processes nodes level-by-level and efficiently computes these averages?

easy

A. Depth-first search (DFS) without tracking levels, summing all nodes and dividing by total count.

B. Breadth-first search (BFS) using a queue to traverse nodes level-by-level, summing values per level and dividing by the number of nodes at that level.

C. Greedy approach that picks the maximum node value at each level and averages those maximums.

D. Dynamic programming that stores partial sums of subtrees and combines them bottom-up.

Solution

1. Step 1: Understand the problem requires level-wise aggregation

   The problem asks for averages per level, so nodes must be grouped by their depth in the tree.

2. Step 2: Identify BFS as the natural approach for level order traversal

   BFS uses a queue to process nodes level-by-level, allowing summing and counting nodes at each level before moving on.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   BFS naturally groups nodes by level, enabling correct average calculation [OK]

Hint: Level order traversal = BFS with queue [OK]

Common Mistakes:

• Using DFS without level tracking loses level grouping
• Greedy max per level ignores all other nodes
• Bottom-up DP is unnecessary and complex here

2. You need to traverse a binary tree level by level, but alternate the order of nodes between left-to-right and right-to-left on each level. Which approach guarantees an optimal solution that avoids reversing lists after each level?

easy

A. Use a breadth-first search with a deque, appending nodes at either end depending on the current level's direction.

B. Perform a standard level order traversal using a queue and reverse the list of nodes at every other level after traversal.

C. Use a depth-first search with recursion, collecting nodes by depth and reversing every other level after traversal.

D. Use two stacks to alternate the order of node processing between levels, pushing children in specific order to maintain zigzag pattern.

Solution

1. Step 1: Understand the zigzag requirement

   The problem requires alternating the traversal direction at each level, which reversing after traversal can achieve but is inefficient.

2. Step 2: Identify approach that avoids reversing

   Using two stacks allows pushing children in an order that naturally produces the zigzag pattern without reversing lists.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two stacks method directly controls order -> no reversing needed [OK]

Hint: Two stacks avoid reversing by controlling push order [OK]

Common Mistakes:

• Assuming reversing after BFS is optimal
• Using DFS and reversing levels post-traversal

3. Consider the following Python code for N-ary tree level order traversal. Given the tree root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)]), what is the value of res after the first iteration of the outer while loop completes?

easy

A. [[1]]

B. [[1, 3, 2, 4]]

C. [[3, 2, 4]]

D. [[5, 6]]

Solution

1. Step 1: Trace the first outer loop iteration

   Initially, current_level contains only the root node with value 1.

2. Step 2: Collect values and enqueue children

   We pop node 1, append its value to level_nodes -> [1], and enqueue its children (3, 2, 4) into next_level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After first iteration, res = [[1]] as only root level processed [OK]

Hint: First level contains only root node value [OK]

Common Mistakes:

• Confusing first level with all children nodes

4. You are given a perfect binary tree where each node has two children. The task is to connect each node's next pointer to its immediate right neighbor on the same level, or NULL if there is none. Which approach guarantees an optimal solution with O(1) extra space and O(n) time complexity?

easy

A. Use the already established next pointers to traverse each level and connect children without extra space.

B. Perform a level order traversal using a queue to connect nodes at each level.

C. Apply a dynamic programming approach to store and connect nodes level-wise.

D. Use a depth-first search recursion to connect nodes from top to bottom.

Solution

1. Step 1: Understand the problem constraints

   The tree is perfect, so every node has two children, and all leaves are at the same level.

2. Step 2: Identify the approach that uses constant extra space

   Using next pointers already set on the current level to connect the next level avoids extra data structures like queues.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses existing pointers to traverse levels [OK]

Hint: Use next pointers to traverse levels without extra space [OK]

Common Mistakes:

• Assuming BFS with queue is optimal space-wise
• Confusing DFS recursion with constant space
• Using DP which is unrelated

5. What is the time complexity of the optimal BFS with column tracking and ordered map approach for vertical order traversal of a binary tree with n nodes and k distinct columns?

medium

A. O(n log n)

B. O(n)

C. O(n log k)

D. O(k log n)

Solution

1. Step 1: Identify main operations

   Each node is processed once (O(n)). For each node, insertion into ordered map (SortedDict) costs O(log k) where k is number of columns.

2. Step 2: Combine complexities

   Total time is O(n) * O(log k) = O(n log k). Sorting all nodes (O(n log n)) is avoided here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Ordered map insertion dominates, giving O(n log k) [OK]

Hint: Ordered map insertion per node costs log k, not log n [OK]

Common Mistakes:

• Assuming O(n) ignoring map insertion cost
• Confusing k (columns) with n (nodes) in complexity