Right side view
Stand to the right of a binary tree and look at it. On every level (all the nodes at the same distance from the root) you see exactly one node: the one furthest to the right. It hides the rest of its level.
Your function gets the tree's root. Return the values you see, one per level, from the root's level down. An empty tree (root is None) gives [].
The node you see is not always a right child. When the right side of the tree stops early, the lower levels are seen through nodes that hang on the left side.
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing.
root = [6, 2, 9, 1, 4, None, None, None, None, 3]Output[6, 9, 4, 3]The levels, left to right, are [6], [2, 9], [1, 4] and [3]. 9 has no children, so the two lowest levels are seen through 4 and 3, which hang under the 2.
root = [5, 3, None, 8]Output[5, 3, 8]Below the root every node is a left child, and every node is alone on its level, so you see all of them.
root = []Output[]No nodes, nothing to see.
0 ≤ number of nodes ≤ 1.3 × 105
-104 ≤ node value ≤ 104
The tree is at most 500 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.