Minimum Depth of Binary Tree

Easy

Extra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.

Question

Given the root of a binary tree, return the smallest number of nodes you'd cross walking from the root down to any leaf.

A leaf is a node that has no children of its own.

Input: root = [8, 15, 25, None, None, 12, 6]

Output: 2

The node 25 has a child, so it isn't a leaf. Its children, 12 and 6, are both leaves reached after just one step down from the root.

Input: root = [50, 30, 70]

Output: 2

Both 30 and 70 are leaves one step below the root.

Input: root = [20, 30]

Output: 2

30 is the only leaf in the tree, and it sits one step below the root, so the shortest path still has to reach it.

What are some questions you'd ask an interviewer?

Why is a plain min(left_depth, right_depth) + 1 formula risky for this problem?

It's fine, that formula always works.

A node with a single child can make that formula pick a side with no leaf at all.

It only breaks for empty trees.

It only breaks for trees with duplicate values.

Take a moment to understand the problem and think of your approach before you start coding.