Binary Tree Right Side View

1. Problem & Core Objective

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

      1            <- 1
     / \
    2   3          <- 3
     \   \
      5   4        <- 4

Output: [1, 3, 4]

Constraints: 0 <= nodes <= 100 · -100 <= Node.val <= 100

What's actually being tested: whether you reframe "what's visible from the right" into "the last node of each level". Once you make that translation, it's question 8 with one line changed. The trap is assuming it means "walk down the right spine".

2. First-Principles Thought Process

The reframe

"Visible from the right" sounds geometric, but it isn't. At each level, exactly one node is rightmost, and it blocks everything behind it. So:

The right side view is the last node of every level.

That's the whole problem. The rest is a level-order traversal you already have.

The trap: it is NOT the right spine

The obvious-looking answer — follow root.right until null — is wrong:

      1
     / \
    2   3
     \
      5        right spine: 1, 3.  Correct answer: 1, 3, 5.

Node 3 has no children, so level 2's only node is 5, which lives in the left subtree. It's visible because nothing is to its right.

So a level can be represented by a node from anywhere in the tree. Any solution that only walks right will miss these.

Two ways to express it

BFS — take the element at index size − 1 in each level. Direct, and it reads exactly like the reframe.

DFS — visit right before left, and record the first node seen at each depth. Since the rightmost branch is explored first, the first arrival at any depth is the rightmost node there.

Both are O(n). The BFS version is more obviously correct; the DFS version is shorter and is O(h) rather than O(w).

3. Solution Paths

Approach 1 — Follow the right spine (the wrong answer, worth discussing)

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    for (TreeNode n = root; n != null; n = n.right) result.add(n.val);
    return result;
}

• Time O(h) · Space O(1) · Correct: no

Counter-questions on this approach

⭐ "Give me an input where this fails."

[1,2,3,null,5] — root 1, children 2 and 3, and node 2 has a right child 5. The right spine is 1, 3 and stops, because 3 is a leaf. But level 2 does contain a node — 5 — and nothing sits to its right, so it's visible. The correct answer is [1,3,5].

The flaw is assuming visibility follows the right pointer. It follows the right position within a level, and the rightmost node at some depth may descend from a left child.

"Is it ever right?"

Only when every level's rightmost node happens to be on the right spine — for instance a perfect tree, or any tree where the right subtree is at least as deep as the left at every node. That's a narrow special case, and relying on it is exactly the bug.

"What's the useful lesson?"

That the problem is about levels, not about pointers. Making that translation explicitly — "visible from the right" means "last node of each level" — is what turns it into a solved problem.

Approach 2 — BFS, take the last of each level (optimal for clarity)

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

    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (i == size - 1) result.add(node.val);     // the last one on this level
            if (node.left  != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }
    return result;
}

Trace — [1,2,3,null,5,null,4]:

Result [1,3,4] ✓

• Time O(n) · Space O(w)

Counter-questions on this approach

⭐ "This is question 8 with one line changed. Is that the point?"

Yes, and it's worth saying out loud. The level-order skeleton is the reusable asset; the variation is only which element of each level you keep. Last gives the right view, first gives the left view, the maximum gives largest-per-level, the mean gives level averages.

Recognising that saves you from re-deriving BFS every time.

⭐ "Why i == size - 1 rather than checking whether the queue is empty?"

Because the queue isn't empty at that point — it already holds the next level's children, enqueued during this loop. The only reliable marker for "last node of this level" is the loop index against the snapshotted size.

Using q.isEmpty() would only ever fire on the final level of the tree.

"Could you just keep overwriting a variable and record it after the loop?"

Yes — assign last = node.val every iteration and add it after the inner loop. Identical result, one fewer comparison per node. Both are fine; the i == size - 1 form makes the intent visible at the point it matters.

"Does this handle a level whose rightmost node comes from a left subtree?"

Yes, and that's the whole advantage over the spine approach. The queue holds every node at a level in left-to-right order regardless of parentage, so index size − 1 is genuinely the rightmost — wherever it came from.

Approach 3 — DFS, right first, record the first at each depth

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);   // first node seen at this depth
    dfs(node.right, depth + 1, result);                 // RIGHT before left
    dfs(node.left,  depth + 1, result);
}

• Time O(n) · Space O(h) stack

Counter-questions on this approach

⭐ "Why does visiting right first make the first node at a depth the rightmost?"

Because the traversal explores the entire right subtree before touching the left. So among all nodes at a given depth, the ones in the right subtree are all reached before any in the left — and within each subtree the same rule applies recursively.

That means the first node reached at depth d is the rightmost at depth d. Swapping the two recursive calls turns this into the left side view, which is a good check that the reasoning is understood rather than memorized.

⭐ "What is depth == result.size() doing?"

It fires exactly once per depth — the first time that depth is reached. Because depths are visited in increasing order with no gaps, result always holds exactly d entries when depth d is first reached.

After that, result.size() exceeds depth and later nodes at the same depth are ignored, which is what you want since only the first one is visible.

"Which would you submit?"

Either, and I'd mention both. BFS states the reframe directly — "last of each level" — and is harder to get subtly wrong. DFS is shorter and is O(h) rather than O(w), so it wins on wide shallow trees. At n <= 100 it makes no practical difference.

"Is this still O(n) even though most nodes are ignored?"

Yes — every node is visited, and the visit is O(1). The if skips the recording, not the traversal. There's no way to skip nodes entirely, since you can't know a subtree contains no new depth without descending into it.

Comparison

4. Why the Optimal Wins

The spine approach is fast and wrong — it confuses "the right pointer" with "the rightmost position", and any tree whose left subtree is deeper exposes it.

Between BFS and DFS it's a genuine tie on time, and a trade on space: O(w) against O(h). I'd write BFS because it restates the reframe literally, and mention DFS as the answer for a wide tree.

The framing worth keeping:

"Visible from the right" means "last node of each level". Translate the geometric wording into a level statement, and the problem becomes a traversal you already have.

Most of the value in this question is that translation — and the fact that the level-order skeleton from question 8 is reusable with one line changed.

5. Java Prerequisites

Selecting the last element of a level

if (i == size - 1) result.add(node.val);   // inside the snapshotted for-loop

First-arrival recording in DFS

if (depth == result.size()) result.add(node.val);

Valid only because depths are reached in increasing order with no gaps.

Recursion order is the algorithm here. dfs(right) then dfs(left) gives the right view; swapping gives the left view. Nothing else changes.

Reuse the level-order skeleton from question 8 rather than rewriting it.

6. Interview Communication Guide

Clarifying questions: Top-to-bottom order (yes)? Is a node visible if it's the rightmost at its level but in a left subtree (yes — this is the crux; confirm it)? What should a null root return (an empty list)?

The pitch

"First I'd reframe it: standing on the right, at each level exactly one node is rightmost and it hides everything behind it. So the answer is the last node of every level.

That reframe matters, because the tempting answer — walk down root.right until null — is wrong. Take a root with children 2 and 3 where 3 is a leaf and 2 has a right child 5. The right spine gives [1,3], but level 2 does have a node, 5, and nothing is to its right, so it's visible. The correct answer is [1,3,5]. Visibility follows position within a level, not the right pointer.

So: level-order BFS, and in each level take the element at index size − 1. That's the traversal from the previous question with one line changed.

O(n) time, O(w) space.

There's a neat DFS alternative — recurse right before left, and record the first node seen at each depth. Because the right subtree is fully explored first, the first arrival at any depth is the rightmost node there. It's O(h) instead of O(w), so better on wide shallow trees. And swapping the two recursive calls gives you the left side view, which is a nice check that the idea generalizes."

Edge cases to volunteer:

Name [1,2,3,null,5]. It's the counterexample to the spine approach, and the only edge case that really matters here — the last two rows show why the wrong solution survives casual testing.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the LEFT side view instead."

BFS: take index 0 instead of size − 1. DFS: recurse left before right. One line either way, which is the clearest evidence that the level reframe was the real content.

⭐ "Return the BOTTOM view — for each horizontal position, the lowest node."

Genuinely different. Track a horizontal distance — left child is hd − 1, right child is hd + 1 — and keep a map from hd to the deepest node seen there. BFS is essential, because with DFS you'd have to compare depths explicitly; with BFS the last write at each hd is automatically the deepest. Then read the map in hd order.

"Return the top view."

Same horizontal-distance map, but keep the first node written at each hd rather than the last, and BFS again guarantees that's the shallowest.

"Count the visible nodes rather than listing them."

That's just the number of levels — the height. Each level contributes exactly one visible node. A pleasing simplification and a good sanity check on the reframe.

"What if the tree were extremely wide?"

BFS holds a whole level at once, so O(w) could be huge. The DFS version is O(h), which is far smaller for a wide shallow tree, and that's when I'd switch.

"Do it for an n-ary tree."

BFS is unchanged — enqueue all children and take the last of each level. DFS needs the children iterated in reverse so the rightmost is visited first. Worth noting, because it's the same "order the recursion" idea generalized.