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:
rootof 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:
- Empty Tree: If the root is null, return an empty list
[]. - Single Node: The result should be
[root.val]. - 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).
- 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”.
- 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. - 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
dbefore moving to depthd+1. - 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).
- Initialize an empty
resultlist and add the root node to the queue if it exists. - 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).
- Determine how many nodes are currently in the queue; this represents the number of nodes at the current level (let’s call this
- Iterate exactly
level_sizetimes:- Pop a node from the front of the queue (
current_node).
- Pop a node from the front of the queue (
- 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.
- 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_sizetimes. The last node popped during this iteration belongs to the rightmost position for that depth (assuming we push children left-to-right). - 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:
- Get current queue length (
n). - Initialize
last_val = None(or similar). - Loop
ifrom 0 ton:- Pop node. Update
last_val = node.val. - Push left child if exists.
- Push right child if exists.
- Pop node. Update
- After inner loop, append
last_valto result.
Complexity Analysis
- Time Complexity: 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: 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 .
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 (
rootisNone): 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