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:

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

Explanation: The shortest path involves root and root.left and has a length of 2.

Example 2:

=> returns 3\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)O(n). The recursion goes through every node in the tree, where nn is the number of nodes.

Space Complexity O(n)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:
Test your code to get an output here!
Test your code to get an output here!