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. 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 can 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:

rightmostLocation(node, location)

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:

rightmostLocation(node, location) = ( 
    max(
        rightmostLocation(node.left, location - 1),
        rightmostLocation(node.right, location + 1)
    )
)

2. Base case

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

# if node has no children (leaf node)
rightmostLocation(node, location) = 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).

rightmostLocation(null, location) = -infinity

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:

def rightmostLocation(root):

    def rightmostLocation(node, location): # our function
        # base case
        if not node:
            return float('-inf')
        if not node.left and not node.right:
            return location

        # recursion
        return max(
            rightmostLocation(node.left, location - 1),
            rightmostLocation(node.right, location + 1)
        )
    
    return rightmostLocation(root, 0) # start out with a location of 0

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.

Here's an alternate solution. You are essentially doing the same thing as above, but without the extra location parameter.

def rightmostLocation(root):
    if not root:
        return float("-inf")
    if not root.left and not root.right:
        return 0
    return max(rightmostLocation(root.left) - 1, rightmostLocation(root.right) + 1)