Stand to the right of a binary tree drawn in the usual way, root at the top, and look at it side-on. On every level you see exactly one node: the rightmost one on that level. It hides everything to its left, even when it hangs from the far left side of the tree.
TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write seen_from_right(root) -> list[int]: the values you see, from the top level down. An empty tree (None) shows nothing.
# 1
# / \
# 2 3
# / \
# 4 5
# /
# 6
seen_from_right(root) # [1, 3, 5, 6]
seen_from_right(None) # []
- Up to 150,000 nodes; values are arbitrary integers and may repeat.
- Trees can be up to 3,000 levels deep. If you recurse, raise the limit first (
sys.setrecursionlimit(10_000)), or use an explicit queue or stack. - Aim for O(n). Walking the tree again for every level is too slow on tall trees.
Show hint
Visit the tree one level at a time and keep the last node of each level. Or walk depth-first, trying the right child before the left, and record the first node you meet at each new depth.