Binary Tree Right Side View

Binary Tree Right Side View asks what you would see standing to the right of a tree: one node per level, the rightmost one. It is a clean excuse to practice breadth-first search level by level — a workhorse pattern for tree problems.

The slow way first

A first instinct is to recurse and somehow track depth and horizontal position, then sift out the rightmost node per depth at the end. That works, but the bookkeeping is fiddly and easy to get wrong. The cleaner mental model is to walk the tree one full level at a time and simply grab the last node of each level.

The question to ask: which node on a level is visible from the right? The last one, when the level is read left to right. If we process levels in order, the answer falls out for free.

The idea: BFS, keep the last of each level

Use breadth-first search. Hold the current level as a list of nodes. Read it left to right; the last node is the one visible from the right, so append its value to the answer. While scanning, collect the next level (each node's left child then right child). Repeat until there are no more nodes.

The key insight: because we read each level left to right, the last node we touch is automatically the rightmost — no coordinates or depth math needed.

Walk through it

Step through the animation. Each level lights up as we scan it. When the level is fully scanned, its rightmost node turns green and its value joins view. Level 0 gives 1, level 1 gives 3 (2 is hidden behind it), level 2 gives 4 (5 is hidden). The result is [1, 3, 4].

Pseudocode

if the tree is empty: return []
view = []
queue = [root]
while queue is not empty:
    level = queue            # this whole level
    queue = []               # start collecting the next level
    for i, node in level (left to right):
        if node is the last in level:
            append node.val to view
        push node.left, then node.right onto queue (if they exist)
return view

The Python solution

def right_side_view(root):
    if not root:
        return []
    view, queue = [], [root]
    while queue:
        level = queue
        queue = []
        for i, node in enumerate(level):
            if i == len(level) - 1:
                view.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
    return view

• queue holds the nodes of the current level; we swap it into level and start a fresh queue for the next one.
• enumerate(level) reads the level left to right, giving us the index i.
• i == len(level) - 1 is true only for the last node of the level — that is the rightmost one we can see.
• We push node.left then node.right, so the next level is also built left to right, keeping the invariant.
• When queue empties, every level has been processed and view is the answer.

Complexity

We touch every node exactly once, so time is O(n). The extra space is the queue, which in the worst case holds the widest level — up to O(n) for a full tree.

When this pattern shows up

Practice