Minimum Depth of Binary Tree - Video Solutions

Problem Overview: Given the root of a binary tree, return the minimum depth. The minimum depth is the number of nodes along the shortest path from the root to the nearest leaf node (a node with no children).

Approach 1: Breadth-First Search (BFS) (Time: O(n), Space: O(n))

Breadth-first search processes the tree level by level using a queue. Start by pushing the root node with depth 1 into the queue. At each step, pop the front node, check if it is a leaf (both left and right children are null), and return the current depth immediately. Because BFS explores nodes level-wise, the first leaf encountered is guaranteed to be the minimum depth. This approach is often preferred because it stops early without traversing the entire tree in many cases.

The algorithm repeatedly performs enqueue operations for left and right children while tracking the depth for each node. In the worst case you visit every node once, giving O(n) time complexity. The queue can hold up to one full level of the tree, leading to O(n) space in a wide tree. This approach relies on standard Breadth-First Search traversal on a Binary Tree.

Approach 2: Depth-First Search (DFS) (Time: O(n), Space: O(h))

Depth-first search explores each path from root to leaf using recursion or an explicit stack. Recursively compute the minimum depth of the left and right subtrees, then return 1 + min(leftDepth, rightDepth). The tricky part is handling nodes that have only one child. If one subtree is null, you must continue through the non-null subtree instead of taking the minimum with zero.

DFS visits every node once, resulting in O(n) time complexity. The recursion stack depth equals the tree height h, which leads to O(h) space. In a balanced tree this is O(log n), but in a skewed tree it can reach O(n). This method uses classic Depth-First Search traversal and is easy to implement recursively.

Recommended for interviews: BFS is usually the expected approach because it naturally finds the closest leaf first and avoids unnecessary traversal. Interviewers like it because it demonstrates understanding of level-order traversal and early termination. Showing the DFS solution still helps demonstrate strong recursion fundamentals and a solid grasp of binary tree edge cases.