Binary Tree Right Side View

MEDIUM✓ CHIP-TIMEDLC #199 — FULL STATEMENT ↗

The drill: Stand to the right of the tree and list every node you can actually see — one value per depth, whichever node is furthest right at that floor.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and the task is to list exactly what you'd see standing to the right of it and looking straight across — one value per depth level, whichever node sits furthest to the right at that level.

A level can lean entirely left with nothing on its right side at all, and the node furthest right that's still visible from outside at that depth is still the one that counts, even when it's the only node on that level.

An empty tree produces an empty list, since there's no depth at all to report a rightmost node for.

EX 01

root = []

→ []

EMPTY TREE

EX 02

root = [1]

→ [1]

SINGLE NODE

EX 03

root = [1, 2, 3, null, 5, null, 4]

→ [1, 3, 4]

LEFT CHILD PEEKS THROUGH A GAP

the tree can hold anywhere from zero to a few thousand nodes
node values can be negative, zero, or positive
exactly one value is reported per depth level, ordered root-level first downward

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

You need exactly one value per depth: the rightmost node reachable at that depth, even if the tree leans left there.

HINT 2 THE STRUCTURE

If you visit right children before left ones, the FIRST node you ever reach at a new depth is guaranteed to be that depth's rightmost node.

HINT 3 ONE STEP FROM THE ANSWER

DFS(node, depth): if depth equals the answer list's current length, this is the first arrival at that depth — record it. Then recurse right before left.

COACH'S BOARD — THE PATTERN, STEP BY STEP

STANDING ON THE RIGHTPATTERN · RIGHT-FIRST DFSroot = [1, 2, 3, null, 5, null, 4]

STEP 1

Visit right child before left, and record a depth only the FIRST time it's reached — that first arrival is always the rightmost node.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/binary-tree-right-side-view.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result: List[int] = []

        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if not node:
                return
            if depth == len(result):     # first arrival at this depth
                result.append(node.val)
            dfs(node.right, depth + 1)   # right first, so it wins the "first arrival"
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return result

TIME O(N)SPACE O(H)PYTHON · RACE PACE · 14 LN

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        def height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))

        h = height(root)
        result = []
        for d in range(h):
            last = [None]

            def walk(node: Optional[TreeNode], depth: int) -> None:
                if not node:
                    return
                if depth == d:
                    last[0] = node.val   # left-to-right order means the last write wins
                walk(node.left, depth + 1)
                walk(node.right, depth + 1)

            walk(root, 0)
            result.append(last[0])
        return result

TIME O(N·H)SPACE O(N)PYTHON · TRAINING PACE · 26 LN

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int depth, List<Integer> result) {
        if (node == null) {
            return;
        }
        if (depth == result.size()) {
            result.add(node.val);
        }
        dfs(node.right, depth + 1, result);
        dfs(node.left, depth + 1, result);
    }
}

TIME O(N)SPACE O(H)JAVA · RACE PACE · 18 LN

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        int h = height(root);
        for (int d = 0; d < h; d++) {
            Integer[] last = new Integer[1];
            walk(root, 0, d, last);
            result.add(last[0]);
        }
        return result;
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    private void walk(TreeNode node, int depth, int target, Integer[] last) {
        if (node == null) {
            return;
        }
        if (depth == target) {
            last[0] = node.val;
        }
        walk(node.left, depth + 1, target, last);
        walk(node.right, depth + 1, target, last);
    }
}

TIME O(N·H)SPACE O(N)JAVA · TRAINING PACE · 33 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED