Recursion

Given the root node of a binary tree `root`

, find the shortest path between the root node and a leaf node, and return its length.

A "leaf" node is defined as a node without any children.

**Example 1:**

$\notag
\large \texttt{=> returns 2}$

**Explanation:** The shortest path involves `root`

and `root.left`

and has a length of 2.

**Example 2:**

$\notag
\large \texttt{=> returns 3}$

First Few Test Cases:

1. Recursion

To solve this problem, you should write a recursion for the minimum root-to-leaf length `minLength(root)`

. The minimum length down to a leaf must include the current node, and it either goes down through the left node or the right node, whichever length is shorter. Here's the recursion:

2. Base case

The recursion should stop when it reaches a leaf node. In this case, the min path down has a length of 1 (the path is just the 1 node we're standing on).

The recursion might also reach a null node. This happens when a node only has 1 child, like in this tree:

It's impossible to reach a leaf node by starting at a null node, so we should completely ignore this case. We can do this by setting the result equal to infinity, so that it gets ignored. This is because a value of infinity will always be ignored inside of a minimum.

3. Code

To code this up, you combine the recursion and base case:

Time Complexity $O(n)$. The recursion goes through every node in the tree, where $n$ is the number of nodes.

Space Complexity $O(n)$. For now, you don't need to know where this comes from - we'll go over the full details in the next lesson "Call Stack". Just know the computer needs some memory to keep track of the function calls it's making.

Mark as Completed: