Problem Statement

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.

Link To the Problem

Intuition

When viewing a binary tree from the right side, at each level of the tree, we only see the rightmost node. So, if we traverse the tree level by level (using Breadth-First Search), the last node encountered at each level will be visible from the right side.

Approach

1. Use a queue (deque) to perform a level-order traversal (BFS).

2. For each level:

   • Process all nodes currently in the queue (those belonging to the same level).

   • Keep track of the last node’s value encountered at this level — that node will be visible from the right side.

3. Add the value of the rightmost node from each level to the result list.

4. Return the result list after the traversal is complete.

Complexity

• Time complexity: Each node is visited exactly once, so the complexity is O(n) where n is the number of nodes

• Space complexity: O(w) where w is the maximum width of the tree (worst-case O(n) for a complete tree), due to the queue used in BFS.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque

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

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

        while q:
            n = len(q)
            for i in range(n):
                node = q.popleft()
                # If it's the last node in this level, add it to the result
                if i == n - 1:
                    res.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

        return res