#199
Binary Tree Right Side View
Medium Rightmost per level
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Imagine standing to the right of the tree. Return the values you can see, from top to bottom.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the last node of every level.
Why this works: DFS that visits right before left; the first node reached at each depth is the one you see.
Example: 1 (2 (-, 5), 3 (-, 4))
depth 0: 1, depth 1: 3, depth 2: 4 → [1, 3, 4]✦Hints open one at a time
You see exactly one node per level: the rightmost.
DFS visiting right before left: the first node you reach at each depth is the visible one.
↗Approach
DFS(node, depth) with right child first. If depth == result size, this is the first node seen at that depth — add it.
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
dfs(root, 0, res);
return res;
}
private void dfs(TreeNode n, int depth, List<Integer> res) {
if (n == null) return;
if (depth == res.size()) res.add(n.val); // first node at this depth
dfs(n.right, depth + 1, res); // right first
dfs(n.left, depth + 1, res);
}
}!Common mistake
Only following right children — a deeper left subtree can be visible below a short right side.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon