Right Side View LeetCode 199 Deep Dive

LeetCode 199 — Binary Tree Right Side View — asks you to imagine standing on the right side of a binary tree and looking inward. You should return the values of the nodes you can see, ordered from top to bottom. The key insight is that from the right side, you see exactly one node per level: the rightmost node at that depth. If a level has only a left child and no right child, that left child is still visible because it is the rightmost node on its level.

This problem is a classic tree traversal exercise that tests whether you understand both BFS level-order traversal and DFS depth tracking. Both approaches solve it cleanly, but they operate on different mental models — BFS thinks in terms of levels, while DFS thinks in terms of depth. Understanding both reveals how the same problem can be modeled from different perspectives.

The constraints are straightforward: the tree can have 0 to 100 nodes, and node values are in the range [-100, 100]. The expected output is a list of integers representing the rightmost node values from top to bottom. An empty tree returns an empty list.

The BFS (breadth-first search) approach processes the tree level by level using a queue. At each level, all nodes are dequeued and their children enqueued. After processing every node in a level, the last node processed is the rightmost node on that level — it is the value visible from the right side. Add that last value to the result list and continue to the next level.

This approach is the most natural match for the problem statement. The concept of "what you see from the right side" maps directly onto "the last node processed at each BFS level." There is no ambiguity and no edge case to reason through — BFS inherently processes nodes from left to right within a level, so the final node at each level is always the rightmost.

BFS runs in O(n) time since every node is visited exactly once. Space is O(w) where w is the maximum width of the tree — the largest number of nodes on any single level. For a complete binary tree this is O(n/2) at the last level, which is O(n). For a skewed tree it is O(1). In practice, the queue holds at most one full level of nodes at any point during traversal.

The BFS implementation uses a queue initialized with the root. At each iteration, record the current queue length — this is the number of nodes on the current level. Loop that many times, dequeuing each node, enqueuing its children, and tracking the last value seen. After the inner loop, append the last value to the result.

Using a deque (collections.deque in Python) for the queue gives O(1) popleft operations, avoiding the O(n) cost of popping from the front of a plain list. In Java, ArrayDeque is the standard choice. The level-size variable is the key implementation detail — it freezes the count of nodes at the start of each level, so adding children during the same iteration does not inflate the loop count.

The total time complexity is O(n) and space complexity is O(w) for the queue, where w is the maximum width. Every node is enqueued and dequeued exactly once. The result list grows by one element per level, so its space usage is O(h) where h is the tree height — O(log n) for balanced trees, O(n) for skewed.

The DFS (depth-first search) approach uses pre-order traversal but visits the right child before the left child. A depth parameter tracks the current level. When the depth equals the length of the result list, this is the first time a node at this depth has been visited — because we visit the right subtree first, this node is guaranteed to be the rightmost at that depth. Add it to the result.

The DFS approach is elegant because it avoids the queue entirely. A simple recursive function with a depth counter does all the work. The key insight is the ordering: by visiting right before left at every node, the first node encountered at each new depth is always the rightmost. Subsequent nodes at the same depth (from the left subtree) are ignored because the result list already has an entry for that depth.

DFS runs in O(n) time since every node is visited exactly once. Space is O(h) for the recursion stack where h is the tree height — O(log n) for balanced trees and O(n) for skewed trees. For trees with extreme height, the DFS approach may hit Python's recursion limit. For balanced trees, the DFS space usage is superior to BFS since tree width often exceeds height.

The left side view variant — returning the leftmost visible node at each depth — requires only a mirror change to each approach. In BFS, instead of recording the last node processed per level, record the first node processed per level. Since BFS processes nodes left to right within each level, the first node is always the leftmost.

In DFS, swap the child visiting order: visit the left child before the right child. The same condition depth == len(result) now fires first on the leftmost node at each depth, since the left subtree is explored first. No other logic changes.

Both variants run with identical time and space complexity to the right side view. The left side view question occasionally appears in interviews as a follow-up to verify that you understand why the approach works — not just that you memorized the code. Being able to explain and swap the direction in under a minute demonstrates genuine understanding.

Python BFS: from collections import deque; def rightSideView(root): if not root: return []; result, q = [], deque([root]); while q: level_size = len(q); for i in range(level_size): node = q.popleft(); if node.left: q.append(node.left); if node.right: q.append(node.right); if i == level_size - 1: result.append(node.val); return result. Java BFS uses ArrayDeque<TreeNode> and records queue.peek() at the end of each level.

Python DFS: def rightSideView(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. Java DFS is identical in structure using a List<Integer> result and passing depth as an int parameter. Both O(n) time; BFS O(w) space, DFS O(h) space.

For interviews, BFS is the recommended answer because it is the most readable and directly maps to the problem description. DFS is a strong follow-up or alternative. Mentioning both demonstrates breadth of tree traversal knowledge. If asked for the space-optimal approach for balanced trees, DFS wins since tree height is O(log n) while width can be O(n) at the last level.

Zigzag Level Order Traversal (LeetCode 103) extends BFS level-order by alternating the direction of node collection — left-to-right on even levels, right-to-left on odd levels. The same queue-based skeleton works; add a direction flag that flips each level. Binary Tree Level Order Traversal (LeetCode 102) is the direct predecessor — mastering BFS level-order with level-size tracking is the foundation for both LeetCode 102 and 199.

Maximum Depth of Binary Tree (LeetCode 104) can be solved via BFS by counting the number of levels processed — each level adds one to the depth. The BFS loop structure from the right side view problem adapts directly: instead of recording the last node per level, just count levels. This makes LeetCode 104 a natural companion problem for reinforcing level-order BFS mechanics.

The tree level-order family — LeetCode 102, 103, 107, 199, 513, 515 — forms a cohesive group where each problem applies BFS level-order traversal with a small twist. Building fluency with the queue-plus-level-size pattern unlocks all of them. Combining these BFS problems with the DFS family (Max Depth, Validate BST, Subtree of Another Tree) gives comprehensive coverage of binary tree traversal for top-tier interviews.