Solving tips
- Reframe as 'the rightmost node of every level', which is the last node dequeued in a BFS level (capture it at i == level_size - 1).
- Snapshot level_size before the inner loop since the queue grows as you enqueue children.
- Slick DFS alternative: recurse right child before left and record a node only when depth == len(view), so the first node seen per depth is the rightmost.
- A node with only a left child can still be its level's rightmost; both approaches handle it. Target O(n) time, O(n)/O(h) space.
Problem
You are given the root of a binary tree. Imagine standing to the right of the tree and looking left. Return the values of the nodes you can see, ordered from top to bottom.
In other words, for each depth level of the tree, the visible node is the rightmost one at that level. Return one value per level.
Examples
Example 1
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Level 0: 1. Level 1: nodes 2,3 — rightmost is 3. Level 2: nodes 5,4 — rightmost is 4.
Example 2
Input: root = [1,null,3]
Output: [1,3]
The root 1 has only a right child 3; both are visible from the right.
Example 3
Input: root = [1,2,3,4]
Output: [1,3,4]
Level 0: 1. Level 1: 2,3 → 3. Level 2: only node 4 (left child of 2), so it is the rightmost by default.
Constraints
- The number of nodes is in the range
[0, 100].
-100 <= Node.val <= 100- An empty tree returns an empty list.
Think about it first
Hint 1
The visible node at each depth is the last node you would encounter scanning that level from left to right. So this is really "grab the last node of every level."
Hint 2
A breadth-first (level-order) traversal processes the tree one level at a time. If you know how many nodes are in the current level, the last one you dequeue is the rightmost.
Hint 3
Alternatively, do a DFS that visits the right child before the left, and record a node's value only the first time you reach a new depth — the first node seen at each depth from a right-first DFS is the rightmost one.
TL;DR
BFS taking the last node of each level (or right-first DFS recording the first node per depth) — O(n) time, O(n) space.
Approach 1 — BFS level order, keep the last of each level
The insight: the right-side view is exactly the rightmost node of every level, so process the tree level by level and record the final node dequeued for each level. Breadth-first search (BFS) uses a queue to visit all nodes at depth d before any at depth d+1.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from typing import Optional, List
from collections import deque
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
view: List[int] = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1: # last node of this level
view.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return view
Walkthrough on Example 1 ([1,2,3,null,5,null,4]):
- Queue
[1], size 1. i = 0 is last → record 1. Enqueue 2, 3.
- Queue
[2,3], size 2. i = 0: node 2, enqueue its right child 5. i = 1: node 3 is last → record 3, enqueue its right child 4.
- Queue
[5,4], size 2. i = 0: node 5. i = 1: node 4 is last → record 4.
- Result
[1,3,4]. ✓
Complexity: O(n) time — every node enqueued and dequeued once. O(n) space for the queue (up to a full level, which can be ~n/2 nodes).
Approach 2 — DFS, right child first, one value per new depth
The insight: if you recurse into the right subtree before the left and record a node only the first time you reach a given depth, that first node is guaranteed to be the rightmost at its level. This trades the queue for the recursion stack.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from typing import Optional, List
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
view: List[int] = []
def dfs(node: Optional[TreeNode], depth: int) -> None:
if not node:
return
if depth == len(view): # first node reached at this depth
view.append(node.val)
dfs(node.right, depth + 1) # right before left
dfs(node.left, depth + 1)
dfs(root, 0)
return view
Walkthrough on Example 3 ([1,2,3,4], where 4 is the left child of 2):
dfs(1, 0): len(view) == 0 == depth → record 1. Recurse right into 3, then left into 2.dfs(3, 1): len(view) == 1 == depth → record 3. Node 3 has no children.- Back to
dfs(2, 1): len(view) == 2 != 1 → skip (depth 1 already filled by 3). Recurse right (None), then left into 4.
dfs(4, 2): len(view) == 2 == depth → record 4.- Result
[1,3,4]. ✓
Complexity: O(n) time, O(h) space for the recursion stack (h = height; O(n) worst case, O(log n) balanced).
Common pitfalls
- Recording the wrong node in BFS: the visible node is the last dequeued in the level (
i == level_size - 1), not the first. Capturing level_size before the inner loop is essential — the queue grows as you enqueue children.
- DFS visiting left first: if you recurse left before right, the “first node at each depth” becomes the leftmost, giving the left-side view. The right-first order is what makes it work.
- A node with only a left child: its left child can still be the rightmost at its level (Example 3). Both approaches handle this — BFS because it is simply the last dequeued, DFS because no right-side node filled that depth first.
- Empty tree: return
[]; the BFS guard (if not root) and the DFS null check both cover it.
Pattern takeaway
“One node per level” problems (right/left view, level maxima, level averages) are natural fits for BFS with a captured level size. When you would rather avoid a queue, a DFS that fixes child order and gates writes on “first time at this depth” (depth == len(result)) achieves the same per-level selection using the call stack.