Binary Tree Right Side View

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. The rightmost node at each level is visible.

Example 1

Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] Explanation: Level 0: 1 (rightmost = 1). Level 1: 2,3 (rightmost = 3). Level 2: 5,4 (rightmost = 4).

Example 2

Input: root = [1,null,3] Output: [1,3]

Constraints:

0 <= Number of nodes <= 100
-100 <= Node.val <= 100

Solution: BFS Level Order
Complexity Analysis

Solution: BFS Level Order

Perform a standard level-order BFS. For each level, the last node dequeued is the rightmost visible node: add its value to the result.

Algorithm:

Enqueue the root.
For each level, snapshot levelSize = queue.size().
Dequeue all levelSize nodes, enqueue their children left-before-right.
After processing the level, the last dequeued node is the rightmost: record its value.

Java

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        TreeNode last = null;

        for (int i = 0; i < levelSize; i++) {
            last = queue.poll();
            if (last.left  != null) queue.offer(last.left);
            if (last.right != null) queue.offer(last.right);
        }

        result.add(last.val); // rightmost node at this level
    }
    return result;
}

Trace through Example 1: root = [1,2,3,null,5,null,4]

Level	Nodes processed	Rightmost
0	1	1
1	2, 3	3
2	5, 4	4

Complexity Analysis

Time: O(n). Every node is enqueued and dequeued exactly once.
Space: O(n). The queue holds at most n/2 nodes at the widest level.