# Min Root to Leaf Length

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:
Submits:
minLength
Imports:
TreeNode
Test your code to get an output here!
minLength(
)
Test your code to get an output here!