Binary Tree Right Side View (BFS)

Medium~20 min

Given the root of a binary tree, imagine yourself standing on the right side of it. Return the values of the nodes you can see ordered from top to bottom.

In other words, return the rightmost node at each level of the tree.

Solve this problem using BFS (level-order traversal) — process each level with a queue and extract the last node at each level.

Each node has a val (integer value), a left child, and a right child. Children may be null.

The tree is given as a level-order array where null represents a missing node. For example, [1,2,3,null,5,null,4] represents:

        1
       / \
      2   3
       \   \
        5   4

Standing on the right side, you see nodes 1, 3, 4 (the rightmost node at each depth level).

Examples

Example 1
Input: root = [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]
Explanation: At depth 0 you see 1, at depth 1 you see 3 (rightmost), at depth 2 you see 4 (rightmost).
Example 2
Input: root = [1, null, 3]
Output: [1, 3]
Explanation: At depth 0 you see 1, at depth 1 you see 3.
Example 3
Input: root = []
Output: []
Explanation: An empty tree has no visible nodes.

Constraints

  • The number of nodes in the tree is in the range [0, 100]
  • -100 <= Node.val <= 100
  • Expected time complexity: O(n)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run