Binary Tree Right Side View
The briefingthe full drill, in my own words
The drill: Stand to the right of the tree and list every node you can actually see — one value per depth, whichever node is furthest right at that floor.
A binary tree arrives, and the task is to list exactly what you'd see standing to the right of it and looking straight across — one value per depth level, whichever node sits furthest to the right at that level.
A level can lean entirely left with nothing on its right side at all, and the node furthest right that's still visible from outside at that depth is still the one that counts, even when it's the only node on that level.
An empty tree produces an empty list, since there's no depth at all to report a rightmost node for.
- the tree can hold anywhere from zero to a few thousand nodes
- node values can be negative, zero, or positive
- exactly one value is reported per depth level, ordered root-level first downward
The hintstake only what you need
HINT 1 THE NUDGE
You need exactly one value per depth: the rightmost node reachable at that depth, even if the tree leans left there.
HINT 2 THE STRUCTURE
If you visit right children before left ones, the FIRST node you ever reach at a new depth is guaranteed to be that depth's rightmost node.
HINT 3 ONE STEP FROM THE ANSWER
DFS(node, depth): if depth equals the answer list's current length, this is the first arrival at that depth — record it. Then recurse right before left.
Coach's boardthe pattern, step by step
Visit right child before left, and record a depth only the FIRST time it's reached — that first arrival is always the rightmost node.
The splitstwo paces, two languages
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
result: List[int] = []
def dfs(node: Optional[TreeNode], depth: int) -> None:
if not node:
return
if depth == len(result): # first arrival at this depth
result.append(node.val)
dfs(node.right, depth + 1) # right first, so it wins the "first arrival"
dfs(node.left, depth + 1)
dfs(root, 0)
return resultclass Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
def height(node: Optional[TreeNode]) -> int:
if not node:
return 0
return 1 + max(height(node.left), height(node.right))
h = height(root)
result = []
for d in range(h):
last = [None]
def walk(node: Optional[TreeNode], depth: int) -> None:
if not node:
return
if depth == d:
last[0] = node.val # left-to-right order means the last write wins
walk(node.left, depth + 1)
walk(node.right, depth + 1)
walk(root, 0)
result.append(last[0])
return resultclass Solution {
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);
}
dfs(node.right, depth + 1, result);
dfs(node.left, depth + 1, result);
}
}class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
int h = height(root);
for (int d = 0; d < h; d++) {
Integer[] last = new Integer[1];
walk(root, 0, d, last);
result.add(last[0]);
}
return result;
}
private int height(TreeNode node) {
if (node == null) {
return 0;
}
return 1 + Math.max(height(node.left), height(node.right));
}
private void walk(TreeNode node, int depth, int target, Integer[] last) {
if (node == null) {
return;
}
if (depth == target) {
last[0] = node.val;
}
walk(node.left, depth + 1, target, last);
walk(node.right, depth + 1, target, last);
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED