Binary Tree Right Side View: BFS Level Order vs. DFS in an Interview
3 views
The problem (LeetCode 199): given the root of a binary tree, imagine standing on its right side and return the values you can see, ordered top to bottom. For the tree 1 -> (2, 3), 2 -> (null, 5), 3 -> (null, 4), the answer is [1, 3, 4]. It looks simple, but it is a favorite screening question because it checks whether you really understand level-order traversal.
A common wrong answer
Many candidates walk only the right children. That fails as soon as a left subtree is deeper than the right one: in the tree 1 -> (2, 3) with 2 -> (4, null), the node 4 is visible from the right even though it is a left child. Say this edge case out loud before you code; interviewers like hearing that you tested the obvious idea and rejected it.
Approach 1: BFS by level
Process the tree one level at a time and record the last node of each level.
from collections import deque
def right_side_view(root):
if not root:
return []
result, q = [], deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i == size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
Time is O(n) and extra space is O(w), where w is the maximum width of the tree. The trick is freezing size = len(q) before the inner loop so you know where a level ends.
Approach 2: DFS, right child first
Visit the right child before the left and track depth. The first node you reach at each new depth is the visible one.
def right_side_view_dfs(root):
result = []
def dfs(node, depth):
if not node:
return
if depth == len(result):
result.append(node.val)
dfs(node.right, depth + 1)
dfs(node.left, depth + 1)
dfs(root, 0)
return result
This uses O(h) stack space, which is better on wide, shallow trees but can overflow on a degenerate tree of height 10^5 in Python.
Follow-ups to expect
- Left side view: record i == 0 instead, or visit left first in DFS.
- Level averages or largest value per level: same BFS skeleton, different aggregation.
- Bottom view or vertical order: now you need horizontal distance, a different problem.
How to present it
Start with the wrong right-children idea, break it with a small example, then give BFS as your main solution and DFS as an alternative with its trade-off. Finish by walking the sample tree through your code. If you blank on the size-freezing detail under pressure, a real-time assistant such as Linkjob AI (https://linkjob.ai) can give you quiet hints during live technical interviews so you stay on track while still explaining the reasoning in your own words.