Domain 2MediumCORE

Binary Tree Right Side View

We are given a binary tree and asked to return an array of node values representing what would be visible from the right side looking at the tree.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Tree#Depth-first Search#Breadth-first Search#Recursion#Queue

199. Binary Tree Right Side View

Model: qwen3.5:9b
Topics: Tree,Depth-first Search,Breadth-first Search,Recursion,Queue
FAANG asked: 1
Acceptance rate: 56.5%


Problem Breakdown

We are given a binary tree and asked to return an array of node values representing what would be visible from the right side looking at the tree.

Key Logic: If you stand on the right, for every horizontal level (depth) in the tree, only one specific node is “visible” — specifically, the rightmost node at that depth. All nodes to its left are occluded by it.

Inputs & Outputs:

  • Input: root of a binary tree (TreeNode). Can be empty (None).
  • Output: A list of integers representing values from top (depth 0) to bottom, containing exactly one value per level.

Edge Cases/Constraints:

  1. Empty Tree: If the root is null, return an empty list [].
  2. Single Node: The result should be [root.val].
  3. Skewed Trees: A tree with only left children or right children must still correctly identify the single visible node per level (which might differ depending on traversal order).
  4. Values: Negative values are allowed, but don’t affect logic; they just need to be stored in a list.

Intuition

The core requirement is “one value per depth”.

  1. Brute Force Idea: We could traverse the tree and store every node at each level in an array (e.g., level_map[depth] = [node_vals...]). After traversing, we iterate through this map and pick the last element for each key. This works but adds unnecessary storage overhead during traversal if not careful.
  2. Key Insight: We need to process nodes strictly level-by-level. If we use a Breadth-First Search (BFS), we naturally encounter all nodes at depth d before moving to depth d+1.
  3. Selection Strategy: Within each BFS iteration for a specific level, the last node processed is guaranteed to be the rightmost one because standard queue traversal processes left-to-right children first. Therefore, if we capture the value of every node in a current-level list and append only the last element’s value to our result array at the end of that loop, we get exactly what we need.

Approach

We will use Level Order Traversal (BFS) using a queue (collections.deque).

  1. Initialize an empty result list and add the root node to the queue if it exists.
  2. While the queue is not empty:
    • Determine how many nodes are currently in the queue; this represents the number of nodes at the current level (let’s call this level_size).
  3. Iterate exactly level_size times:
    • Pop a node from the front of the queue (current_node).
  4. Inside that loop, we need to add children back into the queue for future levels. Crucially, we only care about capturing the value when it’s time to record the rightmost view.
  5. To simplify logic: We can simply append every node popped from this level iteration to a temporary list (or just track the last one). However, since we want only the right side, and standard BFS adds left then right children… wait, if I add both children, the order in queue is Left-Child -> Right-Child. When processing that specific level’s nodes from the front of the queue, they come out in a specific order? Actually simpler logic: Iterate level_size times. The last node popped during this iteration belongs to the rightmost position for that depth (assuming we push children left-to-right).
  6. Append the value of the last processed node at each level to our final result list immediately after finishing the inner loop or track it inside a variable right_most.

Refined Step: Inside the outer while loop:

  1. Get current queue length (n).
  2. Initialize last_val = None (or similar).
  3. Loop i from 0 to n:
    • Pop node. Update last_val = node.val.
    • Push left child if exists.
    • Push right child if exists.
  4. After inner loop, append last_val to result.

Complexity Analysis

  • Time Complexity: O(N)O(N) where N is the number of nodes in the tree. We visit every node exactly once because we process each level fully before moving deeper.
  • Space Complexity: O(W)O(W) where W is the maximum width (number of nodes at any single level) required to store elements in our queue during BFS traversal. In the worst case (a complete binary tree), this approaches O(N/2)O(N/2).

Solution

from collections import deque
# 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

def rightSideView(root: 'TreeNode') -> list[int]:
    # Handle empty input case immediately to avoid queue operations on None
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        
        last_val = None
        
        for _ in range(level_size):
            current_node = queue.popleft()
            
            # Update tracker to be this node's value (it will eventually hold the rightmost)
            last_val = current_node.val
            
            if current_node.left:
                queue.append(current_node.left)
            if current_node.right:
                queue.append(current_node.right)
        
        result.append(last_val)
    
    return result

# Example usage logic (not part of function signature usually, but for clarity):
# root = TreeNode(1)
# root.left = TreeNode(2); root.right = TreeNode(3)
# ... etc.

Edge Cases Handled

  • Empty Tree (root is None): The code checks this at the start and returns an empty list immediately, preventing errors with queue operations on null pointers.
  • Single Node: The loop runs once for depth 0, sets last_val, appends to result, then queue empties. Returns [val]. Correct.
  • Left-Heavy Tree (No Right Children): Even if a node has no right child but only left children, the BFS logic still processes nodes level-by-level. The last popped node at that depth is simply the one furthest to the right available in that layer’s queue order. Since we push Left then Right, and pop from front… wait. Correction on Logic: In standard BFS (pushing L then R), if a parent has only a left child: Queue state before level d: [Node_d] -> Pop