← Create New Paste

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.
Created Nov 17, 2026 19:30 Expires Nov 17, 2027 19:30