All problems

Binary Tree Right Side View

Medium · tree bfs

You are given the root of a binary tree. Picture yourself standing on the right of the tree, looking at it side-on. At each level of the tree, you can see only the node that is farthest to the right on that level; any node with another node to its right on the same level is hidden from you.

Return the values of the nodes you can see, from the top level down to the bottom level. That is one value per level. If the tree is empty, return an empty list.

Note that the node you see on a level is not always a right child. If a level has no node on the right, you see the next one along to the left.

Examples

Example 1

Input: root = [5, 3, 8, 1, 4, 7, 9]

Output: [5, 8, 9]

On the bottom level the nodes are 1, 4, 7 and 9, and 9 is the farthest to the right.

Example 2

Input: root = [1, 2, 3, 4]

Output: [1, 3, 4]

The bottom level holds only the node 4, a left child, and nothing stands to its right, so it is visible.

Example 3

Input: root = []

Output: []

Constraints