Binary Tree Right Side View
Problem Statement
Given the root of a binary tree, imagine standing on the right side of it. Return the values of the nodes you can see from top to bottom.
Input
The root of a binary tree, such as [1,2,3,null,5,null,4].
Output
A list containing one visible value per depth, ordered from the root level down to the deepest visible level.
Constraints
- •
0 <= number of nodes <= 100 - •
-100 <= Node.val <= 100
Examples
Example 1
root = [1,2,3,null,5,null,4]
[1,3,4]Example 2
root = [1,null,3]
[1,3]Example 3
root = []
[]Learning Objectives
- Recognise right-side view as one value per BFS level.
- Use the last node processed in each fixed-size level as the visible node.
- Understand the equivalent DFS strategy: visit right before left and record the first node at each depth.
- Explain why a left subtree can still contribute to the right-side view when no right-side node exists at that depth.
Intuition
Pattern Recognition
The prompt says right side, but the answer is still organised by depth: exactly one visible node per level. That is a level-sweep signal. If you perform normal BFS left-to-right, the rightmost visible node for a level is simply the last node removed from that level.
The common trap is following only right pointers. A node deep in a left subtree may be visible if there is no right-subtree node at that same depth. The rule is not always go right; the rule is for each depth, take the rightmost node that exists. BFS does that by taking the last node of each level. DFS can also do it by visiting right children first and recording the first value seen at each depth.
Common mistakes
- ×Walking only through **node.right** and missing visible nodes that live in left subtrees.
- ×Taking the first node of each left-to-right BFS level instead of the last.
- ×Adding every leaf instead of one node per depth.
- ×Forgetting the empty-tree case and returning a list containing a placeholder.
Algorithm Explanation
Key idea
Use the standard BFS level sweep. At each level, the nodes are processed left-to-right. The final node processed in that fixed-size level is the rightmost node at that depth, so append only that value. The queue still enqueues left child then right child.
Level-by-level walkthrough
Use [1,2,3,null,5,null,4]. Start with queue [1]. The level size is 1, so 1 is both first and last; append 1. Enqueue 2 then 3, so the next queue is [2,3].
The next level size is 2. Poll 2 first and enqueue 5. Poll 3 second and enqueue 4. Because 3 was the last node of this level, append 3. The next queue is [5,4].
At the final level, poll 5 then 4. The last node is 4, so append 4. The visible list is [1,3,4]. Notice that 5 was still visited, but it was hidden by 4 at the same depth.
Algorithm
- Create an empty answer list.
- If root is null, return it.
- Add root to a queue.
- While the queue is not empty, save the current levelSize.
- Poll exactly levelSize nodes from left to right, enqueueing each node left child then right child.
- When the loop index is the final node of the level, append that node value to the answer.
- Return the answer after all levels finish.
Solutions
Solution 1: BFS taking the last node per level
Use this as the primary interview solution when the level-order pattern is obvious. It is iterative and mirrors the visual definition of rightmost node per depth.
Run the fixed-size BFS level template. Within each level, process nodes left-to-right and append the value only when the current index is the last index of that level.
Step-by-step
- Return an empty list for a null root.
- Add root to the queue.
- For each level, store levelSize = queue.size().
- Poll exactly levelSize nodes and enqueue children left-to-right.
- If the node is at index levelSize - 1, append its value because it is the rightmost node for that level.
O(n)
O(width)
Every node is visited once, and the BFS queue is bounded by the maximum level width.
Java implementation
Solution 2: DFS right-first by depth
Use this when the interviewer asks for a recursive solution or when you want to show the depth-first view of the same invariant.
Visit the right subtree before the left subtree. The first time DFS reaches a depth, that node is the rightmost node seen from that level, so record it and ignore later nodes at the same depth.
Step-by-step
- Start DFS at root with depth 0 and an empty view list.
- If the current node is null, return.
- If depth equals the current size of the view list, append the node value because this is the first node reached at that depth.
- Recurse into node.right first.
- Recurse into node.left second so it fills only depths not already covered by the right side.
O(n)
O(h)
Every node is visited once, and recursion uses stack space proportional to the tree height.
Java implementation
Dry Run
Sample input
root = [1,2,3,null,5,null,4]. BFS records the last node processed at each level.
| level | queue before level | nodes processed | last node | view after level |
|---|---|---|---|---|
| 0 | [1] | 1 | 1 | [1] |
| 1 | [2,3] | 2, 3 | 3 | [1,3] |
| 2 | [5,4] | 5, 4 | 4 | [1,3,4] |
The value 5 is visited, but 4 appears later in the same level, so 4 is the node visible from the right at depth 2.
Interview Tips
Lead with BFS because the phrase right side view is one visible value per level. Then mention the elegant DFS variant: visit right first, and when depth == answer.size(), record the node. Also say why walking only right pointers is wrong: a left subtree can be visible when the right side is missing at that depth.
Likely follow-ups
- How would you return the left side view instead?
- How would you return both the leftmost and rightmost values of every level?
- How would the DFS variant change if you wanted the left side view?
- Can you compute the right side view while streaming level order output?
Similar Problems
Key Takeaways
- Right side view is a per-level selection problem, not a right-pointer walk.
- In left-to-right BFS, the last node of each level is the visible rightmost node.
- The DFS alternative visits right before left and records the first node at each depth.
- A left subtree can contribute to the view when no right-side node exists at that depth.