Problem

Given the root of a binary tree, return the values of the nodes that are visible when looking at the tree from the right side, ordered from top to bottom.

Example

Input:
        1
      /   \
     2     3
      \     \
       4     5

Output:
[1,3,5]

From the right side:

  • Level 0 → 1
  • Level 1 → 3
  • Level 2 → 5

Key Observation

At every level of the tree, only the rightmost node is visible.

This immediately suggests using Breadth-First Search (Level Order Traversal) because BFS naturally processes one level at a time.

Once we've finished visiting a level, we simply record its last node.

Approach 1 — Store the Entire Level

The simplest solution is to perform a normal level-order traversal.

For each level:

  1. Visit every node.
  2. Store the node values in a temporary list.
  3. After finishing the level, append the last value.
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        res = []
        queue = deque([root])

        while queue:
            level = []

            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            res.append(level[-1])

        return res

Dry Run

Tree:

        1
      /   \
     2     3
      \     \
       4     5

Level 1

Queue:

[1]

Process:

level = [1]

Take last element:

res = [1]

Level 2

Queue:

[2,3]

Process:

level = [2,3]

Take last element:

res = [1,3]

Level 3

Queue:

[4,5]

Process:

level = [4,5]

Take last element:

res = [1,3,5]

Done.

Time Complexity

Every node is visited once.

Time: O(n)

Space Complexity

The queue stores at most one level of the tree.

Space: O(w)

where w is the maximum width of the tree.

In the worst case:

O(n)

Approach 2 — More Memory Efficient

Notice something interesting.

We don't actually need to store every value in level.

We only care about the last node processed at each level.

So instead of building a list, we can simply detect when we're visiting the final node.

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        res = []
        queue = deque([root])

        while queue:
            length = len(queue)

            for i in range(length):
                node = queue.popleft()

                if i == length - 1:
                    res.append(node.val)

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

        return res

Instead of this:

level = [2,3]
res.append(level[-1])

we simply do:

if i == length - 1:
    res.append(node.val)

No temporary list is needed.

Why This Works

BFS processes nodes from left to right within each level.

For example:

Queue:

2   3

Processing order:

2

3  ← last node

Since the last node processed is the rightmost node of that level, that's exactly the one visible from the right side.

DFS Alternative

This problem can also be solved with Depth-First Search.

The idea is to:

  • Traverse right before left.
  • Keep track of the current depth.
  • The first node visited at each depth is the visible one.

Since DFS reaches the rightmost nodes first, recording the first node encountered at every depth produces the correct answer.

Many interviewers accept either BFS or DFS, but BFS is often the most intuitive solution because the problem is naturally about processing the tree level by level.

Interview Tips

  • Recognize that this is a level-order traversal problem.
  • Use BFS to process one level at a time.
  • The answer for each level is simply its last node.
  • You can either:
    • Store the whole level and take level[-1], or
    • More efficiently, record the last node directly while iterating.
  • Both approaches run in O(n) time, but the second avoids the unnecessary temporary list.

Final Takeaway

Whenever a binary tree problem asks for something "per level", BFS should be one of your first thoughts.

For the right side view:

  • Traverse level by level.
  • The last node of every level is visible from the right.
  • Record it and continue.

It's a clean and efficient O(n) solution that's commonly expected in interviews.