Loading…

mediumTreesLC #199Frequently asked

Binary Tree Right Side View

Q: How do you solve Binary Tree Right Side View using the BFS — Last Node of Each Level approach?

When to use it: Natural first answer: 'right side view = the last node in each level of a level-order traversal'. This builds directly on level-order traversal. We process the tree one level at a time; the visible node for a level is simply the last one we touch in that level. **Reusing the level-size snapshot.** As in level-order traversal, we read `levelSize = queue.size()` before draining a level so children don't leak in. Within the level loop we don't need the whole row — we just remember the most recent node, and after the loop the last one remembered is the rightmost. (Enqueueing left-then-right means the last dequeued is the furthest right.) **Why the last node is the visible one.** Because we enqueue children left before right at every step, each level enters the queue in left-to-right order. Draining the level in FIFO order means the final dequeued node sits furthest right — exactly what an observer on the right sees. **This handles the shorter-right-subtree case for free.** We never assume the visible node descends from a right child. If only a left-subtree node exists at some depth, it's still the last (and only) node dequeued for that level, so it's correctly recorded. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Binary Tree Right Side View using the DFS Right-First — First Node Per Depth (Optimal Space) approach?

When to use it: The elegant answer. 'Visit right before left; the first node I reach at each new depth is the rightmost.' Instead of materializing each level, we let recursion order do the selection. Visiting the right child first guarantees the first node we ever reach at a depth is the rightmost one. **Why right-before-left works.** Pre-order DFS reaches a node before any of its descendants. If at each node we recurse into the right subtree first, then among all nodes at a given depth the one encountered earliest is the furthest right. So 'first node seen at depth d' equals 'rightmost node at depth d'. **The 'new depth' test.** We keep `view` where `view[d]` is the rightmost node at depth d. When we descend to depth `d` and `len(view) == d`, it means we have not recorded depth `d` yet, so this node — the first arrival — is the rightmost. We append it. Every later node at depth `d` finds `len(view) > d` and is skipped. **Why this nails the trap case.** Suppose the right subtree is shorter. At the deeper levels the right side has no nodes, so the first (and only) arrivals at those depths come from the left subtree — and the `len(view) == depth` test records them. We never assume the visible node is a right child. **Space win.** DFS only keeps a root-to-leaf path on the stack, O(h), versus BFS holding a full level, O(width). For balanced trees the widest level is ~n/2, so DFS can be markedly leaner. Time complexity: O(n). Space complexity: O(h).

LCPractice

Trees & BST · 10 of 41 · 8 min

Given the root of a binary tree, imagine yourself standing on the **right side** of it. Return the values of the nodes you can see ordered from **top to bottom**.

For each level of the tree, the visible node is the one furthest to the right at that depth.

In plain English

For every depth, exactly one node is visible from the right: the rightmost one at that depth. The result lists those rightmost nodes from the top level down. Crucially, the visible node may come from a left subtree if the right subtree doesn't reach that depth.

Examples

Example 1

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Note: Level 0: 1. Level 1: rightmost is 3. Level 2: 5 (under 2) and 4 (under 3); rightmost is 4.

Example 2

Input: root = [1,2,3,4]
Output: [1,3,4]
Note: Level 2 has only node 4 (left child of 2). The right subtree (3) has no children, so the left-subtree node 4 is the visible one.

Example 3

Input: root = []
Output: []
Note: Nothing to see.

Constraints

The number of nodes is in the range [0, 100]
-100 ≤ Node.val ≤ 100
The tree may be empty

Clarifying questions4First question: Is it the right spine of the tree or the rightmost node per level?Explore questions

Q1.Is it the right spine of the tree or the rightmost node per level?
Rightmost per level. If the right subtree is shorter than the left, the deeper visible nodes come from the left subtree — so it's not simply the right edge.
Q2.Top-to-bottom order?
Yes — index 0 is the root (the only level-0 node), then the rightmost of each successive level downward.
Q3.Can the tree be empty?
Yes. Return an empty list and guard the null root.
Q4.Are values unique?
Not guaranteed, but it doesn't matter — we select by position (rightmost), not by value.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Standing on the right of the tree, you see exactly one node per level — the rightmost one at each depth. Two clean ways: BFS by level and keep the last node dequeued in each level, or DFS visiting right-before-left and recording the first node seen at each new depth. Both are O(n) time; DFS is O(h) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize the answer is the rightmost node per level (not the right spine), and whether you can reduce a level-order traversal to one value per level — via BFS-last or DFS-right-first.

Where candidates slip

Just walking down the right children, which fails when a left subtree extends deeper than the right one and contributes the visible node for those lower levels.

How to stand out

Call out the 'left node visible when right subtree is shorter' case with a concrete example, then give the DFS right-first solution in O(h) space and mention BFS as the equally valid alternative.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	BFS — Last Node of Each Level	`O(n)`	`O(n)`	Natural first answer: 'right side view = the last node in each level of a level-order traversal'.	Read
2	DFS Right-First — First Node Per Depth (Optimal Space)Optimal	`O(n)`	`O(h)`	The elegant answer. 'Visit right before left; the first node I reach at each new depth is the rightmost.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewRightmost node per levelPrefer iterative level handling?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

BFS — Last Node of Each Level

TimeO(n)SpaceO(n)

Natural first answer: 'right side view = the last node in each level of a level-order traversal'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you traversed the tree level by level, which node in each level is the one you'd see from the right?

2Hint 2Explore hint

Run standard BFS with the queue-size snapshot. The last node you dequeue in a level is its rightmost.

3Hint 3Explore hint

During each level's loop, when the index reaches levelSize - 1 (or simply overwrite a variable each iteration), record that node's value.

A · Core idea

This builds directly on level-order traversal. We process the tree one level at a time; the visible node for a level is simply the last one we touch in that level.

Reusing the level-size snapshot. As in level-order traversal, we read levelSize = queue.size() before draining a level so children don't leak in. Within the level loop we don't need the whole row — we just remember the most recent node, and after the loop the last one remembered is the rightmost. (Enqueueing left-then-right means the last dequeued is the furthest right.)

Why the last node is the visible one. Because we enqueue children left before right at every step, each level enters the queue in left-to-right order. Draining the level in FIFO order means the final dequeued node sits furthest right — exactly what an observer on the right sees.

This handles the shorter-right-subtree case for free. We never assume the visible node descends from a right child. If only a left-subtree node exists at some depth, it's still the last (and only) node dequeued for that level, so it's correctly recorded.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

level 0

drain [1] → last is 1

Stateview=[1], queue=[2,3]

Final result[1,3,4]

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full code

solution.javaJava

BFS — Last Node of Each Level — reference

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public List<Integer> rightSideView(TreeNode root) {
9
    List<Integer> view = new ArrayList<>();
10
    if (root == null) {
11
        return view;
12
    }
13
    Queue<TreeNode> queue = new LinkedList<>();
14
    queue.offer(root);
15
    while (!queue.isEmpty()) {
16
        // Snapshot the level boundary before enqueuing children (same as level-order
17
        // traversal).
18
        int levelSize = queue.size();
19
        for (int i = 0; i < levelSize; i++) {
20
            TreeNode node = queue.poll();
21
            // The last node dequeued in the level is its rightmost — that's what's
22
            // visible.
23
            if (i == levelSize - 1) {
24
                view.add(node.val);
25
            }
26
            // Left before right means the last dequeued is furthest right.
27
            if (node.left != null) queue.offer(node.left);
28
            if (node.right != null) queue.offer(node.right);
29
        }
30
    }
31
    return view;
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Right side view is 'level-order traversal, but collapse each level to its last element'. That reframing makes the trap (left node visible when the right subtree is shorter) disappear, because BFS-by-level doesn't care which subtree a node came from.

ComplexityO(n) time, O(n) space — Standard BFS visits each node once → O(n) time. The queue can hold a whole level → O(n) space in the worst case.

E · Edge cases and pitfalls3Recording the first node instead of the last (that would be a left-side view).Explore edge cases

Pitfalls

Recording the first node instead of the last (that would be a left-side view).
Re-reading queue size inside the loop, merging levels.
Forgetting the empty-tree guard.

03.2

Approach 2 of 2 · Optimal

DFS Right-First — First Node Per Depth (Optimal Space)

TimeO(n)SpaceO(h)

The elegant answer. 'Visit right before left; the first node I reach at each new depth is the rightmost.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you recurse into the right child before the left child, which node at each depth do you reach first?

2Hint 2Explore hint

Carry a depth argument. The first time you arrive at a given depth, that node is the rightmost for that level.

3Hint 3Explore hint

Compare depth to the size of your result list: if they're equal, you've reached a new depth for the first time — append this node, then recurse right then left.

A · Core idea

Instead of materializing each level, we let recursion order do the selection. Visiting the right child first guarantees the first node we ever reach at a depth is the rightmost one.

Why right-before-left works. Pre-order DFS reaches a node before any of its descendants. If at each node we recurse into the right subtree first, then among all nodes at a given depth the one encountered earliest is the furthest right. So 'first node seen at depth d' equals 'rightmost node at depth d'.

The 'new depth' test. We keep view where view[d] is the rightmost node at depth d. When we descend to depth d and len(view) == d, it means we have not recorded depth d yet, so this node — the first arrival — is the rightmost. We append it. Every later node at depth d finds len(view) > d and is skipped.

Why this nails the trap case. Suppose the right subtree is shorter. At the deeper levels the right side has no nodes, so the first (and only) arrivals at those depths come from the left subtree — and the len(view) == depth test records them. We never assume the visible node is a right child.

Space win. DFS only keeps a root-to-leaf path on the stack, O(h), versus BFS holding a full level, O(width). For balanced trees the widest level is ~n/2, so DFS can be markedly leaner.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Why a left node can be visible

node 1, depth 0

Active call / nodeSupporting contextReturned stateNot active

Right subtree of 1 (node 3) ends at depth 2 via node 4; node 5 under 2 is at the same depth but to its left, so 4 wins level 2.

Final result[1,3,4]

C · Code with teaching comments

solution.javaJava

DFS Right-First — First Node Per Depth (Optimal Space) — optimal

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public List<Integer> rightSideView(TreeNode root) {
9
    List<Integer> view = new ArrayList<>();
10
    dfs(root, 0, view);
11
    return view;
12
}
13
 
14
private void dfs(TreeNode node, int depth, List<Integer> view) {
15
    if (node == null) {
16
        return;
17
    }
18
    // First arrival at this depth → because we go right-first, it's the rightmost node.
19
    if (depth == view.size()) {
20
        view.add(node.val);
21
    }
22
    // Right subtree BEFORE left — this ordering is what makes 'first seen' =
23
    // 'rightmost'.
24
    dfs(node.right, depth + 1, view);
25
    // Left subtree still explored, so it can supply visible nodes where the right
26
    // subtree is shorter.
27
    dfs(node.left, depth + 1, view);
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

Order of recursion is a selection mechanism. By choosing right-before-left, 'first seen at this depth' becomes 'rightmost at this depth' with no comparisons. Swap to left-before-right and the identical skeleton produces the left side view.

ComplexityO(n) time, O(h) space — Each node is visited once → O(n). Only the recursion stack is extra, bounded by the tree height → O(h) space, better than BFS's O(width).

E · Edge cases and pitfalls6root = [1,2,3,4] (4 is left child of 2) — Right subtree (3) is childless; at depth 2 only node 4 exists, and DFS right-first records it → [1,3,4].Explore edge cases

Edge cases handled

root = [1,2,3,4] (4 is left child of 2)Right subtree (3) is childless; at depth 2 only node 4 exists, and DFS right-first records it → [1,3,4].
Left-only spine [1,2,null,3]Each level has one node from the left chain; every one is the rightmost-by-default → [1,2,3].
root = nulldfs returns immediately; view stays empty → [].

Pitfalls

Recursing left before right — produces the LEFT side view.
Using a 'visited depth' set incorrectly; the len(view) == depth test is simpler and correct.
Assuming the answer is the right spine — fails when the left subtree is deeper.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Following only right children

Walking down node.right misses levels where the right subtree is shorter than the left. On [1,2,3,4] the right child of root (3) has no children, but node 4 (left child of 2) is visible at depth 2.

Explore the code comparison

Don't write this

node, view = root, []
while node:                 # only the right spine
    view.append(node.val)
    node = node.right

Write this instead

def dfs(node, depth):
    if not node: return
    if depth == len(view):
        view.append(node.val)
    dfs(node.right, depth + 1)
    dfs(node.left,  depth + 1)

DFS in the wrong child order

If you recurse left before right, the first node recorded at each depth is the leftmost, so you build the left side view instead of the right.

Explore the code comparison

Don't write this

if (depth == view.size()) view.add(node.val);
dfs(node.left, depth + 1, view);   // left first → left view
dfs(node.right, depth + 1, view);

Write this instead

if (depth == view.size()) view.add(node.val);
dfs(node.right, depth + 1, view);  // right first → right view
dfs(node.left, depth + 1, view);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Per-level extremum (rightmost per depth)

Code pattern to memorize

# DFS, right-first
def dfs(node, depth):
    if not node: return
    if depth == len(view): view.append(node.val)  # first at this depth = rightmost
    dfs(node.right, depth + 1)
    dfs(node.left,  depth + 1)

Rules to remember

1The answer is one value per level — the rightmost node at each depth, NOT the right-edge/right-spine of the tree.
2A left subtree node can be visible if the right subtree is shorter — don't just follow right children.
3BFS: take the last node you dequeue in each level. DFS: visit right before left and record the first node at each new depth.
4Track depth so you record exactly one value per level.
5Empty tree → empty list; guard the null root.

Use this pattern when

You need one representative per level (rightmost, leftmost, max, min, average)
'What's visible from one side', 'last/first in each row' style questions
Any level-grouped problem where you collapse each level to a single value
Right-side / left-side view, largest value per row, bottom-up views

Choose another pattern when

You need all nodes per level → full level-order traversal instead
The tree is a pure right spine and you mistakenly think that's always the answer → it isn't when left subtrees go deeper
You need the boundary/outline of the tree → that's the Boundary of Binary Tree problem, different logic

Interview takeaway

The right side view is the rightmost node of each level. Whether you BFS and grab the last per level or DFS right-first and grab the first per depth, the unifying idea is 'collapse each level to one representative'. The visible-from-shorter-left-subtree case is the trap that separates a real understanding from pattern-matching on right children.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPer-level extremum. Collapse each level of a tree to a single representative — rightmost, leftmost, max, or average. The DFS-order-as-selection trick (right-first → rightmost) and the BFS last-per-level trick both reduce to 'one value per depth'. Same family as Largest Value in Each Row and level averages.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Binary Tree Level Order Traversal
The parent pattern — keep every node per level instead of just the last.
Find Largest Value in Each Tree Row
Coming soon
Same per-level collapse, but take the max of each level instead of the rightmost.
Populating Next Right Pointers in Each Node
Coming soon
Level-by-level processing where you link each node to its right neighbour.
Binary Tree Vertical Order Traversal
Coming soon
Group by horizontal column instead of depth — BFS carrying a column index.

Same pattern

←

Binary Tree Level Order Traversal

Continue · Next problem

Kth Smallest Element in a BST

mediumTreesLC #199Frequently asked

Binary Tree Right Side View

LCPractice

Trees & BST · 10 of 41 · 8 min

Given the root of a binary tree, imagine yourself standing on the **right side** of it. Return the values of the nodes you can see ordered from **top to bottom**.

For each level of the tree, the visible node is the one furthest to the right at that depth.

In plain English

Examples

Example 1

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Note: Level 0: 1. Level 1: rightmost is 3. Level 2: 5 (under 2) and 4 (under 3); rightmost is 4.

Example 2

Input: root = [1,2,3,4]
Output: [1,3,4]
Note: Level 2 has only node 4 (left child of 2). The right subtree (3) has no children, so the left-subtree node 4 is the visible one.

Example 3

Input: root = []
Output: []
Note: Nothing to see.

Constraints

The number of nodes is in the range [0, 100]
-100 ≤ Node.val ≤ 100
The tree may be empty

Clarifying questions4First question: Is it the right spine of the tree or the rightmost node per level?Explore questions

Q1.Is it the right spine of the tree or the rightmost node per level?
Rightmost per level. If the right subtree is shorter than the left, the deeper visible nodes come from the left subtree — so it's not simply the right edge.
Q2.Top-to-bottom order?
Yes — index 0 is the root (the only level-0 node), then the rightmost of each successive level downward.
Q3.Can the tree be empty?
Yes. Return an empty list and guard the null root.
Q4.Are values unique?
Not guaranteed, but it doesn't matter — we select by position (rightmost), not by value.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize the answer is the rightmost node per level (not the right spine), and whether you can reduce a level-order traversal to one value per level — via BFS-last or DFS-right-first.

Where candidates slip

Just walking down the right children, which fails when a left subtree extends deeper than the right one and contributes the visible node for those lower levels.

How to stand out

Call out the 'left node visible when right subtree is shorter' case with a concrete example, then give the DFS right-first solution in O(h) space and mention BFS as the equally valid alternative.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	BFS — Last Node of Each Level	`O(n)`	`O(n)`	Natural first answer: 'right side view = the last node in each level of a level-order traversal'.	Read
2	DFS Right-First — First Node Per Depth (Optimal Space)Optimal	`O(n)`	`O(h)`	The elegant answer. 'Visit right before left; the first node I reach at each new depth is the rightmost.'	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

BFS — Last Node of Each Level

TimeO(n)SpaceO(n)

Natural first answer: 'right side view = the last node in each level of a level-order traversal'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you traversed the tree level by level, which node in each level is the one you'd see from the right?

2Hint 2Explore hint

Run standard BFS with the queue-size snapshot. The last node you dequeue in a level is its rightmost.

3Hint 3Explore hint

During each level's loop, when the index reaches levelSize - 1 (or simply overwrite a variable each iteration), record that node's value.

A · Core idea

This builds directly on level-order traversal. We process the tree one level at a time; the visible node for a level is simply the last one we touch in that level.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

level 0

drain [1] → last is 1

Stateview=[1], queue=[2,3]

Final result[1,3,4]

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full code

solution.javaJava

BFS — Last Node of Each Level — reference

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public List<Integer> rightSideView(TreeNode root) {
9
    List<Integer> view = new ArrayList<>();
10
    if (root == null) {
11
        return view;
12
    }
13
    Queue<TreeNode> queue = new LinkedList<>();
14
    queue.offer(root);
15
    while (!queue.isEmpty()) {
16
        // Snapshot the level boundary before enqueuing children (same as level-order
17
        // traversal).
18
        int levelSize = queue.size();
19
        for (int i = 0; i < levelSize; i++) {
20
            TreeNode node = queue.poll();
21
            // The last node dequeued in the level is its rightmost — that's what's
22
            // visible.
23
            if (i == levelSize - 1) {
24
                view.add(node.val);
25
            }
26
            // Left before right means the last dequeued is furthest right.
27
            if (node.left != null) queue.offer(node.left);
28
            if (node.right != null) queue.offer(node.right);
29
        }
30
    }
31
    return view;
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Standard BFS visits each node once → O(n) time. The queue can hold a whole level → O(n) space in the worst case.

E · Edge cases and pitfalls3Recording the first node instead of the last (that would be a left-side view).Explore edge cases

Pitfalls

Recording the first node instead of the last (that would be a left-side view).
Re-reading queue size inside the loop, merging levels.
Forgetting the empty-tree guard.

03.2

Approach 2 of 2 · Optimal

DFS Right-First — First Node Per Depth (Optimal Space)

TimeO(n)SpaceO(h)

The elegant answer. 'Visit right before left; the first node I reach at each new depth is the rightmost.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you recurse into the right child before the left child, which node at each depth do you reach first?

2Hint 2Explore hint

Carry a depth argument. The first time you arrive at a given depth, that node is the rightmost for that level.

3Hint 3Explore hint

Compare depth to the size of your result list: if they're equal, you've reached a new depth for the first time — append this node, then recurse right then left.

A · Core idea

Instead of materializing each level, we let recursion order do the selection. Visiting the right child first guarantees the first node we ever reach at a depth is the rightmost one.

Space win. DFS only keeps a root-to-leaf path on the stack, O(h), versus BFS holding a full level, O(width). For balanced trees the widest level is ~n/2, so DFS can be markedly leaner.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Why a left node can be visible

node 1, depth 0

Active call / nodeSupporting contextReturned stateNot active

Right subtree of 1 (node 3) ends at depth 2 via node 4; node 5 under 2 is at the same depth but to its left, so 4 wins level 2.

Final result[1,3,4]

C · Code with teaching comments

solution.javaJava

DFS Right-First — First Node Per Depth (Optimal Space) — optimal

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public List<Integer> rightSideView(TreeNode root) {
9
    List<Integer> view = new ArrayList<>();
10
    dfs(root, 0, view);
11
    return view;
12
}
13
 
14
private void dfs(TreeNode node, int depth, List<Integer> view) {
15
    if (node == null) {
16
        return;
17
    }
18
    // First arrival at this depth → because we go right-first, it's the rightmost node.
19
    if (depth == view.size()) {
20
        view.add(node.val);
21
    }
22
    // Right subtree BEFORE left — this ordering is what makes 'first seen' =
23
    // 'rightmost'.
24
    dfs(node.right, depth + 1, view);
25
    // Left subtree still explored, so it can supply visible nodes where the right
26
    // subtree is shorter.
27
    dfs(node.left, depth + 1, view);
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(h) space — Each node is visited once → O(n). Only the recursion stack is extra, bounded by the tree height → O(h) space, better than BFS's O(width).

E · Edge cases and pitfalls6root = [1,2,3,4] (4 is left child of 2) — Right subtree (3) is childless; at depth 2 only node 4 exists, and DFS right-first records it → [1,3,4].Explore edge cases

Edge cases handled

root = [1,2,3,4] (4 is left child of 2)Right subtree (3) is childless; at depth 2 only node 4 exists, and DFS right-first records it → [1,3,4].
Left-only spine [1,2,null,3]Each level has one node from the left chain; every one is the rightmost-by-default → [1,2,3].
root = nulldfs returns immediately; view stays empty → [].

Pitfalls

Recursing left before right — produces the LEFT side view.
Using a 'visited depth' set incorrectly; the len(view) == depth test is simpler and correct.
Assuming the answer is the right spine — fails when the left subtree is deeper.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Following only right children

Walking down node.right misses levels where the right subtree is shorter than the left. On [1,2,3,4] the right child of root (3) has no children, but node 4 (left child of 2) is visible at depth 2.

Explore the code comparison

Don't write this

node, view = root, []
while node:                 # only the right spine
    view.append(node.val)
    node = node.right

Write this instead

def dfs(node, depth):
    if not node: return
    if depth == len(view):
        view.append(node.val)
    dfs(node.right, depth + 1)
    dfs(node.left,  depth + 1)

DFS in the wrong child order

If you recurse left before right, the first node recorded at each depth is the leftmost, so you build the left side view instead of the right.

Explore the code comparison

Don't write this

if (depth == view.size()) view.add(node.val);
dfs(node.left, depth + 1, view);   // left first → left view
dfs(node.right, depth + 1, view);

Write this instead

if (depth == view.size()) view.add(node.val);
dfs(node.right, depth + 1, view);  // right first → right view
dfs(node.left, depth + 1, view);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Per-level extremum (rightmost per depth)

Code pattern to memorize

# DFS, right-first
def dfs(node, depth):
    if not node: return
    if depth == len(view): view.append(node.val)  # first at this depth = rightmost
    dfs(node.right, depth + 1)
    dfs(node.left,  depth + 1)

Rules to remember

1The answer is one value per level — the rightmost node at each depth, NOT the right-edge/right-spine of the tree.
2A left subtree node can be visible if the right subtree is shorter — don't just follow right children.
3BFS: take the last node you dequeue in each level. DFS: visit right before left and record the first node at each new depth.
4Track depth so you record exactly one value per level.
5Empty tree → empty list; guard the null root.

Use this pattern when

You need one representative per level (rightmost, leftmost, max, min, average)
'What's visible from one side', 'last/first in each row' style questions
Any level-grouped problem where you collapse each level to a single value
Right-side / left-side view, largest value per row, bottom-up views

Choose another pattern when

You need all nodes per level → full level-order traversal instead
The tree is a pure right spine and you mistakenly think that's always the answer → it isn't when left subtrees go deeper
You need the boundary/outline of the tree → that's the Boundary of Binary Tree problem, different logic

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Binary Tree Level Order Traversal
The parent pattern — keep every node per level instead of just the last.
Find Largest Value in Each Tree Row
Coming soon
Same per-level collapse, but take the max of each level instead of the rightmost.
Populating Next Right Pointers in Each Node
Coming soon
Level-by-level processing where you link each node to its right neighbour.
Binary Tree Vertical Order Traversal
Coming soon
Group by horizontal column instead of depth — BFS carrying a column index.

Same pattern

←

Binary Tree Level Order Traversal

Continue · Next problem

Kth Smallest Element in a BST