Minimum depth of a binary tree
Filed under Goldman Sachs
Free read 3 of 3Define minimum depth: distance from root to the nearest leaf node (a node with no children).
The question
Find the minimum depth of a binary tree, optimizing the traversal so it handles skewed trees efficiently.
Constraints
- Node values are integers
- Tree can be completely balanced or completely skewed
- Minimum depth is defined as the number of nodes along the shortest path from root down to nearest leaf node
Examples
- Input
- root = [3, 9, 20, null, null, 15, 7]
- Output
- 2
- Why
- The shortest path is root (3) -> left child (9) with depth 2.
Approach
Define minimum depth: distance from root to the nearest leaf node (a node with no children).
Standard DFS visiting all nodes and returning the minimum height, but it visits all nodes even if a shallow leaf is found early.
Use Breadth-First Search (BFS) level-order traversal. The moment we encounter the first node with no left and right children, return its depth immediately. This is optimal for skewed trees where the shallow leaf might be near the top.
Empty tree (returns 0), single-node tree (returns 1), and completely skewed trees.
Tips
- What they are testing: Tests tree traversal algorithms (DFS vs BFS) and optimization awareness for skewed structures.
- Common mistake: Using standard recursive DFS without handling nodes that have only one child, which incorrectly counts null branches as depth 1.
Follow-ups
- Optimize DFS to handle skewed trees (proposed BFS / level-order traversal).
Related Goldman Sachs questions
Collected from public candidate posts and coding forums. Updated Nov 2026.