Minimum Depth of Tree

Find the shortest root-to-leaf path in a binary tree.

binary-tree depth traversal recursion

Write a function `min_depth(root)` that takes the root of a binary tree and returns the minimum depth of the tree. The minimum depth is the number of nodes along the shortest path from the root down to the nearest leaf node. A leaf is a node with no children. If the tree is empty, return 0. The binary tree is represented using dictionaries, where each node has keys 'val', 'left', and 'right'. `left` and `right` are either a node dict or None. For example, a single-node tree is {'val': 1, 'left': None, 'right': None}. Implement `min_depth(root)`. The tree can have up to 10,000 nodes. Your solution should run in O(n) time and O(n) worst-case space (or better).

Constraints

Number of nodes in the tree is between 0 and 10,000. Node values are integers. The tree is a binary tree.

Example

>>> root = {'val': 3, 'left': {'val': 9, 'left': None, 'right': None}, 'right': {'val': 20, 'left': {'val': 15, 'left': None, 'right': None}, 'right': {'val': 7, 'left': None, 'right': None}}}
>>> min_depth(root)
2

>>> min_depth(None)
0

>>> root = {'val': 1, 'left': {'val': 2, 'left': None, 'right': None}, 'right': None}
>>> min_depth(root)
2

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

If root is None, return 0.

A node with only one child is not a leaf; you must recurse into that child.

Recursive approach: if both children exist, depth = 1 + min(min_depth(left), min_depth(right)).

Handle the cases where one child is None carefully.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.