Recursion

Tree Right Side View

Given the root of a binary tree root, return an array with the the "right side view" of the tree.

Example:

=> returns [1,3,6]\notag \\[20 bp] \Large \texttt{=> returns [1,3,6]}
First Few Test Cases:

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:

queue = [1]                                                                  queue = [2, 3]\notag \large \texttt{queue = [1]} \;\;\;\;\;\;\; \xrightarrow{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}\;\;\;\;\;\;\;\texttt{queue = [2, 3]}

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

queue = [2, 3]                                                                  queue = [4, 5, 6]\notag \large \texttt{queue = [2, 3]} \;\;\;\;\;\;\; \xrightarrow{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}\;\;\;\;\;\;\;\texttt{queue = [4, 5, 6]}

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:

Mark as Completed:
Submits:
rightSideView
Imports:
TreeNode
Test your code to get an output here!
rightSideView(
)
Test your code to get an output here!