Minimum Depth of Binary Tree - Video Solutions

Problem Overview: You are given the root of a binary tree and need to return its 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). Unlike maximum depth problems, you must stop as soon as the first leaf is encountered.

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

BFS processes the tree level by level using a queue. Start by pushing the root node with depth 1. At each step, remove a node from the queue, check if it is a leaf, and if so return its depth immediately. Otherwise push its left and right children with depth +1. The key insight: the first leaf discovered during level-order traversal must belong to the minimum depth path. Because each node is visited once, the time complexity is O(n), where n is the number of nodes. Space complexity is O(w), where w is the maximum width of the tree. This approach naturally fits problems involving the shortest distance from a root in a tree structure.

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

DFS explores each branch recursively and calculates the minimum depth from children. For every node, compute the minimum of the left and right subtree depths and add one for the current node. The tricky part is handling nodes with only one child: if one subtree is null, you must return the depth of the non-null subtree instead of taking a minimum with zero. Without this condition, the result becomes incorrect for skewed trees. DFS visits every node once, giving O(n) time complexity. The recursion stack uses O(h) space where h is the tree height. This technique commonly appears in recursive problems involving depth-first search on a binary tree.

Recommended for interviews: BFS is usually the expected answer because it naturally finds the shortest path to a leaf and can terminate early once the first leaf is encountered. DFS still demonstrates strong understanding of recursion and tree traversal, but it always explores deeper branches even when a shallow leaf already exists. Showing both approaches during an interview signals that you understand traversal strategies and their tradeoffs.