Binary Tree Right Side View

Problem

Imagine standing to the right of a binary tree and looking at it side-on. At each depth you see exactly one node: the rightmost node on that level, whether or not it is a right child. Given the root, return the values of the visible nodes ordered from the top level down. Return an empty list for an empty tree.

• The tree has at most 3,000 nodes and may be empty.
• Node values are integers; duplicates are allowed.

Examples

• root = [8, 3, 10, None, 6, None, 14] → [8, 10, 14]. At each depth the rightmost node happens to be on the right spine.
• root = [8, 3, 10, 1, None, None, None, 4] → [8, 10, 1, 4]. The 1 and the 4 are left children, but each is the only node on its level, so both are visible from the right.
• root = [2, None, 6] → [2, 6].

Hints

1. Which node on each level is visible? Is it always reachable by only following right pointers?
2. If you had all the nodes grouped by level, the answer is one element from each group.
3. Level-order BFS and take the last node of each level; or a pre-order DFS that visits the right child first and records the first node it reaches at each new depth.