Binary Tree Right Side View LeetCode 199

LeetCode 199 — Binary Tree Right Side View — gives you the root of a binary tree. Imagine standing on the right side of the tree. Return the values of the nodes you can see from top to bottom.

The visible nodes are the rightmost nodes at each level. If a level has nodes [1, 2, 3], only 3 is visible from the right. If a node has no right child but has a left child, the left child might be visible if no right-side node exists at that depth.

Two clean approaches: BFS processes the tree level by level and takes the last node of each level. DFS visits right subtree first and records the first node encountered at each new depth. Both produce the same result in O(n) time.

Use a queue for level-order traversal. Process nodes level by level: for each level, the number of nodes is the current queue size. Process all nodes in the level, and the LAST node processed is the rightmost — add its value to the result.

Implementation: queue = deque([root]). While queue is non-empty: level_size = len(queue). For i in range(level_size): node = queue.popleft(). If i == level_size - 1: result.append(node.val). Add node's children to the queue (left first, then right).

The BFS approach is intuitive: it literally scans each level left to right and picks the last one. It handles all cases naturally, including when the rightmost visible node comes from the left subtree at a deeper level.

DFS with right subtree visited before left. Maintain a result list. At each node, if the current depth equals the length of the result list, this is the first node we have seen at this depth — it must be the rightmost. Append its value.

The recursion visits root (depth 0), right subtree (depth 1), then left subtree (depth 1). Since right is visited first, the first node at any new depth is always the rightmost. Left subtree nodes at the same depth are ignored because the result already has an entry.

This approach uses the recursion stack (O(H) space) and is slightly more elegant than BFS. It naturally handles the case where a left subtree extends deeper than the right — those deeper left nodes are visible since no right node exists at that depth.

Consider tree: 1 (left: 2 with right child 5, right: 3 with right child 4). BFS: Level 0: [1]. Last = 1. result = [1]. Level 1: [2, 3]. Last = 3. result = [1, 3]. Level 2: [5, 4]. Last = 4. result = [1, 3, 4].

DFS right-first: visit 1 (depth 0, result.len=0 → add 1). Visit 3 (depth 1, result.len=1 → add 3). Visit 4 (depth 2, result.len=2 → add 4). Visit null. Back to 1, visit 2 (depth 1, result.len=3 > 1 → skip). Visit 5 (depth 2, result.len=3 > 2 → skip). Result: [1, 3, 4].

Now consider tree: 1 (left: 2 with left child 4, right: 3). Level 0: 1. Level 1: 3 (rightmost). Level 2: 4 (only node at this depth, visible from right even though it is a left child). Result: [1, 3, 4]. DFS handles this because depth 2 has no right-side node, so 4 is recorded first.

Python BFS: from collections import deque. result = []. If not root: return []. queue = deque([root]). While queue: level_size = len(queue). For i in range(level_size): node = queue.popleft(). If i == level_size-1: result.append(node.val). If node.left: queue.append(node.left). If node.right: queue.append(node.right). Return result.

Python DFS: 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: same logic with Queue<TreeNode> for BFS or recursive method for DFS. The DFS version is particularly clean in Java — about 10 lines total.

Time complexity is O(n) for both approaches. Every node is visited exactly once. BFS processes each node during its level scan. DFS visits each node once during recursion.

Space complexity: BFS uses O(w) where w is the maximum width of the tree (the largest level). In the worst case (complete binary tree), w = n/2 = O(n). DFS uses O(H) for the recursion stack where H is the tree height. In the worst case (skewed tree), H = n.

Both are O(n) in the worst case. For balanced trees, BFS uses O(n/2) = O(n) (wide levels) while DFS uses O(log n) (short recursion). DFS is slightly better for balanced trees.

Binary Tree Level Order Traversal (LeetCode 102) returns all nodes at each level. Right Side View is a special case: only the last node per level. If you can solve 102, solving 199 is trivial — just take the last element of each level list.

Kth Smallest Element in a BST (LeetCode 230) uses inorder traversal (a different traversal order) to find order statistics. Together with Right Side View (level-order), these cover the two most common tree traversal patterns.

Populating Next Right Pointers (LeetCode 116) also uses level-order traversal to connect nodes at the same level. The BFS level-processing pattern is identical. Mastering one transfers to all of them.