Shortest Downward Trip From the Root to a Leaf
Solve this ProblemYou are given the root of a binary tree. Return the number of nodes on the shortest path that starts at the root and ends at a leaf. A leaf is a node with no children at all; a node that has only one child is not a leaf. For an empty tree, return 0.
The recursive solution must take care with nodes that have a single child. Searching level by level is often simpler, because the first leaf you meet is automatically on the shortest path.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
A leaf is a node with no children at all. Return the number of nodes on the shortest path from the root down to any leaf (0 for an empty tree). A node with only one child is NOT a leaf
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursively Measure Every Root-to-Leaf Path
GoodRecursion follows the definition. An empty tree has depth 0. If a node is missing one child, that side is not a path to a leaf, so the answer must come from the other child: 1 + the answer for it (this rule is the trap — taking the minimum with an empty side would wrongly give 1). If both children exist, take 1 plus the smaller of the two answers. This measures every root-to-leaf path, so it visits all n nodes (O(n) time) with O(h) recursion space.
O(n)O(h)1class Solution {
2 public int shortestLeafPath(TreeNode root) {
3 if (root == null) return 0;
4 if (root.left == null) return 1 + shortestLeafPath(root.right);
5 if (root.right == null) return 1 + shortestLeafPath(root.left);
6 return 1 + Math.min(shortestLeafPath(root.left), shortestLeafPath(root.right));
7 }
8}Optimal — Level by Level, Stop at the First Leaf
OptimalSearch level by level with a queue, counting levels. The first leaf met is on the shallowest level that contains a leaf, so its level number is the answer — no need to look at anything deeper. Each round increases the depth counter, looks at every node of that level, returns immediately if one has no children, and otherwise queues the children for the next level. It has the same O(n) worst case, but on an unbalanced tree that has a shallow leaf it stops early instead of walking the long branches, and there is no deep recursion.
O(n)O(w)1class Solution {
2 public int shortestLeafPath(TreeNode root) {
3 if (root == null) return 0;
4 Queue<TreeNode> queue = new ArrayDeque<>();
5 queue.add(root);
6 int depth = 0;
7 while (!queue.isEmpty()) {
8 depth++;
9 int size = queue.size();
10 for (int i = 0; i < size; i++) {
11 TreeNode node = queue.poll();
12 if (node.left == null && node.right == null) return depth;
13 if (node.left != null) queue.add(node.left);
14 if (node.right != null) queue.add(node.right);
15 }
16 }
17 return depth;
18 }
19}