199. Binary Tree Right Side View

Medium · solved 2026-10-06 · Open on LeetCode

treebinary-treebfs

Time O(n) · Space O(w)

How to get there

Make the rightmost node the first one found

1. Restate what is seen. Looking at the tree from the right, each depth shows exactly one node: the rightmost node at that depth. The answer lists them from the top down.

2. Try the obvious walk and find where it fails. Following right children from the root gives the right edge of the tree. On [1, 2, 3, 4] that is 1, 3, and stops, but the view is 1, 3, 4: the 4 hangs under the left child 2, yet nothing at its depth sits further right, so it is seen. Every depth needs checking, not just the right edge.

3. Walk depth by depth. Breadth-first search takes the tree one level at a time, so it meets every node at every depth. What it must keep is one node per depth: the rightmost.

4. Order the walk so the rightmost comes first. Push each node’s right child before its left. A level then leaves the queue from right to left, so the first child found at the next depth belongs to the rightmost parent that has a child, and it is the right child when there is one: exactly the rightmost node at that depth. Keeping the first node found per depth, with setdefault, keeps the view.

5. Read the answer in depth order. A Python dict keeps insertion order, and each depth is first inserted only after the one above it, so result.values() runs from the top down.

6. Check the cost. Each node is queued once: O(n) time. The queue holds at most about two levels at a time, O(w) for the widest level, and result holds one entry per depth.

The reusable recipe: when you need one extreme node per level, order the walk so that extreme is found first, then keep only the first node found at each depth.

Let the queue's order write the lines

Variable	Always means
`queue`	`(node, depth)` pairs found but not yet expanded, in the order found; within a level, right to left
`result`	for each depth found so far, the first node found there, which is its rightmost

Code	What happened	What it keeps true
`queue, result = deque([(root, 0)]), {0: root}`	depth 0 holds only the root	the root is its own level’s view
`current, depth = queue.popleft()`	the next node, right to left within its level
`queue.append((current.right, depth+1))` first	the right child is found before its sibling	the next level is queued right to left too
`result.setdefault(depth+1, child)`	a child at `depth + 1` is found	the first one found at a depth stays; later, more-leftward ones are ignored
`return [node.val for node in result.values()]`	the queue is empty	one value per depth, top to bottom

The order of the two if blocks is the whole trick. Swap them, pushing the left child first, and the first node found at each depth becomes the leftmost: on [1, 2, 3, null, 5, null, 4] the same code then returns the left side view, [1, 2, 5], instead of [1, 3, 4].

The method carries over: decide which node of each group should be found first, then order the pushes so that it is.

Alternatives compared

Approach	Time	Space	How it works
Follow right children only	O(h)	O(1)	Wrong: it misses deeper nodes in left subtrees, giving [1, 3] instead of [1, 3, 4] on [1, 2, 3, 4].
Level by level, keep the last	O(n)	O(w)	Breadth-first search one level per round with `for _ in range(len(queue))`, pushing left then right, and keep each round’s last node.
First found per depth, right child first (chosen, `solution.py`)	O(n)	O(w)	One breadth-first pass pushing right before left; `setdefault` keeps the first node found at each depth.
Depth-first, right child first	O(n)	O(h)	Visit right before left and append a node’s value when `depth == len(result)`, the first node reached at that depth.

All three correct versions rely on the same idea: walk so that the rightmost node of each depth is reached first, or last, and keep exactly that one. The depth-first version needs only O(h) space, where breadth-first holds a whole level; on a wide, shallow tree that is the difference.

solution.py

# 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
class Solution:
    def rightSideView(self, root: TreeNode | None) -> list[int]:
        if not root:
            return []

        queue, result = deque([(root, 0)]), {0: root}

        while queue:
            current, depth = queue.popleft()

            if current.right:
                queue.append((current.right, depth+1))
                result.setdefault(depth+1, current.right)
            if current.left:
                queue.append((current.left, depth+1))
                result.setdefault(depth+1, current.left)

        return [node.val for node in result.values()]

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.