LeetCode 199 – Binary Tree Right Side View

Right Side View is the clearest illustration of a point Zigzag Level Order made in passing: how you traverse and what you record are independent. The answer is level-order traversal with one line changed — and the DFS solution is a genuinely different idea worth knowing, because it is shorter and it generalises.

The problem

Standing to the right of a binary tree, return the values of the nodes you can see, ordered top to bottom.

    1            <- 1
   / \
  2   3          <- 3
   \   \
    5   4        <- 4      answer: [1, 3, 4]

    1            <- 1
   / \
  2   3          <- 3
 /
4                <- 4      answer: [1, 3, 4]
                            the visible node on the last level is a LEFT child

[]     -> []
[1]    -> [1]

The second example is the one that matters. "Rightmost" means rightmost at that depth, not "keep going right" — a left child is visible whenever nothing to its right exists at the same level. Any solution that just walks down the right spine gets this wrong.

BFS: the last node of each level

Take level order traversal and, instead of collecting the level, record only its final element:

for each level:
    size = queue.size()              the snapshot, as always
    for i in 0..size-1:
        node = queue.poll()
        if (i == size - 1) record node.val      <- the only change
        enqueue children left, then right

The queue is still filled left to right. Nothing about the traversal changes; the recording rule does. That is the whole solution, and saying it in those terms — "this is problem 102 with one line different" — is a better answer than deriving it fresh.

Java

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> visible = new ArrayList<>();
        if (root == null) return visible;

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();      // snapshot: one whole level

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                // The last node of the level is the one you can see.
                if (i == levelSize - 1) visible.add(node.val);

                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }

        return visible;
    }
}

The level-size snapshot is doing the same job as in problem 102 — without it there is no notion of "last on this level" at all, and i == levelSize - 1 is meaningless.

DFS: right first, record the first node at each depth

The other solution is shorter and reads as a different idea. Visit the right subtree before the left, carrying the depth. The first node reached at any depth is, by construction, the rightmost one at that depth:

class Solution:
    def rightSideView(self, root: TreeNode) -> list[int]:
        visible: list[int] = []

        def walk(node: TreeNode, depth: int) -> None:
            if node is None:
                return

            # First arrival at this depth == rightmost, because we go right first.
            if depth == len(visible):
                visible.append(node.val)

            walk(node.right, depth + 1)
            walk(node.left, depth + 1)

        walk(root, 0)
        return visible

depth == len(visible) is the "first arrival" test, and it works because depths are reached in increasing order — you can never skip a level, since reaching depth d + 1 requires passing through d. It also means visible is always exactly as long as the number of levels seen so far, which is a pleasant invariant to state.

Swap the two recursive calls and you get the left side view, which is problem 199's mirror and occasionally the actual question asked. One line.

Python (BFS)

    def rightSideViewBfs(self, root: TreeNode) -> list[int]:
        from collections import deque

        if root is None:
            return []

        visible, queue = [], deque([root])

        while queue:
            level_size = len(queue)

            for i in range(level_size):
                node = queue.popleft()

                if i == level_size - 1:       # last on this level
                    visible.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return visible

Complexity

Both visit every node — you cannot know a level's rightmost node without examining the level. The space differs in the usual way: BFS pays for width, DFS for depth. On a complete tree the last level holds half the nodes, so BFS is the expensive one; on a degenerate tree it is the reverse.

Neither can be improved. Even the rightmost path alone is not enough, as the second example shows.

The pattern

Four problems, one loop, four different lines inside it:

Once the level-size snapshot is automatic, all four are the same five minutes of work. That is the argument for learning problem 102 properly rather than each of these separately.

What the interviewer is checking

• That the visible node may be a left child — the rightmost at its depth, not on the right spine.
• The level-size snapshot, carried over from problem 102.
• That the traversal is unchanged and only the recording rule differs.
• Empty tree returning [].
• A left-only tree, where every visible node is a left child.
• That you can give the DFS version and explain the first-arrival test.
• The O(w) versus O(h) trade between the two.