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.