Problem 31 · Trees

Binary Tree Right Side View

MediumClassic DSA & systems

01Problem

Return the values visible when looking at a binary tree from the right side, top to bottom.

02Key insight

The visible node at each depth is the first one reached by a DFS that visits right before left; record a value the first time a new depth is reached.

03Solution

solution.pypython22 lines

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional

@dataclass
class TreeNode:
    val: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None

def right_side_view(root: Optional[TreeNode]) -> list[int]:
    view: list[int] = []
    stack = [(root, 0)]
    while stack:
        node, depth = stack.pop()
        if not node:
            continue
        if depth == len(view):
            view.append(node.val)
        stack.append((node.left, depth + 1))
        stack.append((node.right, depth + 1))  # popped first: right before left
    return view

Try it first.

TimeO(n)

SpaceO(h)

tests.py · 3 passing

tests.pypython4 lines

T = TreeNode
assert right_side_view(T(1, T(2, None, T(5)), T(3, None, T(4)))) == [1, 3, 4]
assert right_side_view(T(1, T(2, T(4)), T(3))) == [1, 3, 4]
assert right_side_view(None) == []

04Staff-level follow-up

Need left, right, top and bottom views? Top/bottom views require horizontal-distance bucketing via BFS (to respect depth order), not just per-depth first visit.