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:

minLength(root) = 1 + min(
    minLength(root.left),
    minLength(root.right)
)

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).

# leaf node
minLength(leaf) = 1

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.

# null node
minLength(null) = float('inf')

3. Code

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

def minLength(root):
    
    # base case
    if not root:
        return float('inf')
    if not root.left and not root.right:
        return 1

    # recursion
    return 1 + min(
        minLength(root.left),
        minLength(root.right)
    )

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.