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.

Additional information

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Example 1:

Input: root = [1, 2, 3, null, 5, null, 4]

Output: [1, 3, 4]

Example 2:

Input: root = [1, null, 3]

Output: [1, 3]

Example 3:

Input: root = []

Output: []

Iterative Breadth-First Search (BFS) - Optimal

Intuition

The problem asks us to find the rightmost node at every single level of the tree. This screams "Level Order Traversal."
If we use Breadth-First Search (BFS) to process the tree layer by layer (left to right), the very last node we process in any given layer will be the node visible from the right side. We just need to capture that last node's value for each level.

Algorithm

1. If the root is None, return an empty list [].
2. Initialize an empty list res to store the final result.
3. Initialize a queue and append the root.
4. While the queue is not empty:

• Get the current length of the queue (level_size = len(queue)).

• Initialize a variable rightmost_val to keep track of the last value seen in this level.

• Loop level_size times:

• Pop the leftmost node from the queue.

• Update rightmost_val = node.val. (By the end of the loop, this holds the last node's value).

• If it has a left child, append the left child to the queue.

• If it has a right child, append the right child to the queue.

• Append rightmost_val to res.

5. Return res.

def right_side_view(root: Optional[TreeNode]) -> list[int]:
    if not root:
        return []
        
    res = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        rightmost_val = None
        
        for _ in range(level_size):
            node = queue.popleft()
            rightmost_val = node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        res.append(rightmost_val)
        
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit every node in the binary tree exactly once.

• Space complexity: O(n)

• Reason: In the worst-case scenario (a perfectly balanced tree), the bottom-most level contains roughly n/2 nodes, which is the maximum size of our queue.

Recursive Depth-First Search (DFS)

Intuition

We can also solve this using Depth-First Search (DFS). The trick is to prioritize traversing the right side of the tree before the left side (Node -> Right -> Left).
If we keep track of the current depth (level) during our recursion, the first time we reach a new depth, the node we are currently looking at must be the rightmost node for that level.

Algorithm

1. Initialize an empty list res.
2. Create a helper function dfs(node, level):

• If node is None, return.
• If level == len(res), it means we are visiting this depth for the very first time. Since we always explore right branches first, this node is guaranteed to be the rightmost. Append node.val to res.
• Recursively call dfs(node.right, level + 1). (Notice we go right first!)
• Recursively call dfs(node.left, level + 1).

3. Call dfs(root, 0).
4. Return res.

def right_side_view(root: Optional[TreeNode]) -> list[int]:
    res = []
    
    def dfs(node, level):
        if not node:
            return
            
        if level == len(res):
            res.append(node.val)
            
        dfs(node.right, level + 1)
        dfs(node.left, level + 1)
        
    dfs(root, 0)
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: We still visit every node in the tree exactly once.

• Space complexity: O(h)

• Reason: The space is consumed by the recursion stack, which goes as deep as the height h of the tree. In the worst case (skewed tree), this is O(n).