This problem asks us to simulate standing on the right side of a binary tree and report the values of the nodes we can see, ordered from top to bottom. This perspective means for each level of the tree, we are interested in the value of the node that is furthest to the right.

The most intuitive and efficient way to process a tree level by level is using Breadth-First Search (BFS), also known as level-order traversal. This approach naturally explores all nodes at one depth before moving on to the next, making it perfect for identifying the rightmost node at each level.

Intuition:

Imagine a horizontal slice through the tree, representing a single level. When we perform a BFS, we process all nodes in this slice from left to right. If we keep track of the last node encountered at each level, that node will inherently be the rightmost one visible from the right side. This systematic left-to-right processing within each level is key.

We use a queue to manage the nodes to visit. When processing a level, we extract all nodes currently in the queue. For each of these nodes, we add its children to the queue for the next level. By simply updating a variable with each node processed from the current level, the variable will hold the rightmost node's value by the time we finish the level.

Step-by-step thinking:

Initialize an empty list called `result` to store the right-side view values and handle the edge case where the `root` is `null` by returning an empty list.
Initialize a queue (e.g., `LinkedList`) and add the `root` node to it. This queue will manage nodes level by level.
Start a `while` loop that continues as long as the queue is not empty, meaning there are still nodes to process.
Inside the loop, capture the `levelSize` by getting the current size of the queue. This is crucial because it tells us exactly how many nodes belong to the current level.
Initialize a `rightmostNode` variable to `null` before processing each level. This variable will store the last node we encounter at the current level.
Iterate `levelSize` times using a `for` loop. In each iteration, `poll()` a `currentNode` from the queue.
Immediately after polling, assign `currentNode` to `rightmostNode`. Because we process nodes from left to right within a level (due to how BFS generally enqueues children), the last node assigned to `rightmostNode` in this `for` loop will be the true rightmost node of the current level.
If `currentNode` has a `left` child, add it to the queue. If it has a `right` child, add it to the queue. These children will be processed in the next level.
After the `for` loop finishes (meaning all nodes of the current level have been processed), add the `val` of `rightmostNode` to the `result` list. By this point, `rightmostNode` holds the correct rightmost value for the level.
Once the `while` loop completes, return the `result` list.

Time Complexity: O(N), where N is the total number of nodes in the tree. Each node is enqueued and dequeued exactly once.
Space Complexity: O(W), where W is the maximum width of the tree (the maximum number of nodes at any single level). In the worst case (a complete binary tree), W can be N/2, so the space complexity can be O(N).

Learn Complexity

146. Binary Tree Right Side View

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Hint

Use Cases