We can't do a greedy solution that just goes down the rightmost branch, because that branch might end, exposing other branches. We need to traverse the tree layer-by-layer, taking the rightmost node at each layer.

We should use a BFS since a BFS goes layer-by-layer naturally. Here's the code for a BFS from the lesson:

Now, how do we find the rightmost node in each layer of the BFS?

Remember that the line for _ in range(len(queue)) visits nodes layer by layer. For example, here's what the queue looks like after visiting the 1st layer:

And here's what it looks like after visiting the 2nd layer:

The rightmost node is always the last element in the queue, queue[-1]. So to solve the problem, we'll keep an array of all the rightmost nodes we've seen so far in an array, called soln. We just stick a few lines of code into the BFS: