To solve this problem, we want to write a recursion for the rightmost location in the tree, rightmostLocation(node).

It's very difficult to find a recursion for this function - it's actually impossible! The reason is that you need to know the depth of the current node that you're on - it's impossible to know a node's location without passing it down from its parent nodes.

To fix this, you need to add an input to your function, so that the parent nodes can pass the appropriate location down to their children nodes. Here's the function we'll write:

1. Recursion

The rightmost location is equal to whichever is bigger of: the rightmost location in the left tree, and the rightmost location in the right tree. Here's the recursion for this:

2. Base case

The recursion should stop when it reaches a leaf node. In this case, the function should return the current location.

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

In this case, we call $\small \text{rightmostLocation(null)}$. This doesn't make sense - a null tree does not contain any leaf nodes, so we should competely ignore this case We can do this by setting it equal to -infinity so it gets ignored in the maximum (negative infinity is smaller than any number, so it gets ignored in a maximum).

3. Code

To code this up, we can create a recursive function rightmostLocation using our recursion and base case. We can use it to get the solution. Here's the code:

Time Complexity $O(n)$. We visit every node once and do O(1) operations per node, giving O(n)*O(1) = O(n).

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.