Binary Tree Right Side View (LeetCode 199)
Given the root of a binary tree, picture standing to its right and looking across every level. Return the value of the rightmost node visible at each depth, ordered from the top level down to the bottom.
Worked Examples
root = [1,2,3,null,5,null,4][1,3,4]1, then 3, then 4.root = [1,2,3,4,null,null,null,5][1,3,4,5]4 (under 2), so it is visible even though it sits on the left; below it, 5 is visible too.root = [1,null,3][1,3]1 on the top level, then 3.root = [][]⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 100].-100 <= Node.val <= 100
Core Insight
Level snapshots guarantee that the last element popped at depth d is the rightmost visible node.
Real-World Scenario & Production Applications
3D graphic bounding hull projection, tree shadow rendering.
Step-by-Step Execution Trace Table
Step-by-Step Wavefront Progression
- Step 1 (Root Seed, Depth 0, d=0):
queue = [1]. Initialresult = []. - Step 2 (Snapshot Depth 0, level_size=1, d=0):
level_size = 1. Processing node indexi = 0. - Step 3 (Dequeue 1, Record Silhouette, Depth 0, d=0): Pop
1. Sincei == level_size - 1(last node in depth 0), Record1result = [1]. Enqueue left child2and right child3queue = [2, 3]📸. - Step 4 (Snapshot Depth 1, level_size=2, d=1):
level_size = 2. Processing node indexi = 0.queue = [2, 3]. - Step 5 (Dequeue 2, Intermediate Node, Depth 1, d=1): Pop
2. Sincei = 0 != 1, not rightmost visible. Enqueue right child5queue = [3, 5]. - Step 6 (Dequeue 3, Record Silhouette, Depth 1, d=1): Pop
3. Sincei = 1 == level_size - 1, Record3result = [1, 3]. Enqueue right child4queue = [5, 4]📸. - Step 7 (Snapshot Depth 2, level_size=2, d=2):
level_size = 2. Processing node indexi = 0.queue = [5, 4]. - Step 8 (Dequeue 5, Intermediate Node, Depth 2, d=2): Pop
5. Sincei = 0 != 1, not rightmost visible. Node 5 has no children. - Step 9 (Dequeue 4, Record Silhouette, Depth 2, d=2): Pop
4. Sincei = 1 == level_size - 1, Record4result = [1, 3, 4]. Node 4 has no children 📸. - Step 10 (Queue Empty, Complete, d=2):
queue = []. Right silhouette complete. Search Complete: return[1, 3, 4]✅.
root = [1,2,3,null,5,null,4]Expected:[1,3,4]| 1 | queue = deque([root]) |
| 2 | visible = [] |
| 3 | while queue: |
| 4 | level_size = len(queue) |
| 5 | for i in range(level_size): |
| 6 | node = queue.popleft() |
| 7 | if i == level_size - 1: |
| 8 | visible.append(node.val) |
| 9 | append the children of node to queue |
| 10 | return visible |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Imagine standing on the right side of a binary tree looking inward horizontally. At every vertical level , you can only see exactly one node: the rightmost node at that depth. A common blunder is assuming you can simply follow root.right all the way down. If the right subtree terminates early at depth 2 while the left subtree extends down to depth 10, the left subtree's deeper nodes are completely exposed to the right side! Breadth-First Search solves this effortlessly: traverse the tree level-by-level from left to right, and simply sample the final node popped in each level's snapshot loop.
🏟️ The Analogy: Watching a City Skyline from Across the River
Imagine standing on the eastern bank of a river looking at skyscrapers arranged in east-west rows. For each east-west block, the tallest building furthest to the east is the only one visible on the skyline; any shorter buildings behind it are blocked from view. If a block has no tall buildings on the east end, a building on the west end becomes visible. To draw the skyline silhouette, you look along each row from left to right and record the very last building your eyes land on.
🔑 Why It Works
Because the inner loop runs from i = 0 to level_size - 1, the condition i == level_size - 1 is guaranteed to trigger exactly once per level on the rightmost node, automatically capturing deep left-subtree nodes whenever the right subtree is missing.
Selecting the first element instead of last: The rightmost node is the last element processed in a left-to-right level traversal (
level[-1]), or the first in a right-to-left traversal.Assuming right children shadow all left children: If the right subtree is shallower than the left subtree, lower nodes from the left subtree become visible from the right side. Purely following
.rightpointers fails.Storing all level nodes in memory: Storing the full 2D level array when only the final element of each level is needed wastes auxiliary memory.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Collect rightmost silhouette nodes at each depth level.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: the last node processed in a level-order batch of size N is the rightmost node at that depth.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Assuming the right subtree always contains the rightmost node (a deep left child can be visible if right subtree is shallow).
Using DFS without tracking depth levels visited.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use level-order BFS with queue size snapshots. For each level, I iterate through all nodes at that depth; when i == level_size - 1, I append the node value to my visible list. Runs in
O(N)time andO(N)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: BFS traverses each level, taking the last node in each level queue batch and adding it to the result. Total N nodes.
O(W) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Queue holds max width W nodes.
T(N) = O(N)
Derivation Progression
level_size = len(Q)
Batches each depth tier.
if i == level_size - 1: res.append(val)
Extracts the rightmost visible node in O(1).
N nodes = O(N)
Traverses tree in linear time.
Variable Definitions
Total number of nodes in the binary tree
Maximum level width (at most ⌈N/2⌉ nodes)
Tree height (length of output list)
Memory Architecture & Bounds
O(1) Iterative
O(W) BFS queue
O(H) Result array of size equal to tree height
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "right side view", "visible nodes from top to bottom". Silhouette extraction: you can see exactly one node per depth tier. In a standard level-order BFS, the rightmost visible node is the last node processed in that tier ().
. Time budget linear time.
Empty tree root returns []. Skewed left branches that are deeper than right branches: BFS naturally captures them because once the right branch terminates, the left branch becomes the rightmost survivor at deeper levels.
Binary Tree Right Side View (LeetCode 199)
Given the root of a binary tree, picture standing to its right and looking across every level. Return the value of the rightmost node visible at each depth, ordered from the top level down to the bottom.
Worked Examples
root = [1,2,3,null,5,null,4][1,3,4]1, then 3, then 4.root = [1,2,3,4,null,null,null,5][1,3,4,5]4 (under 2), so it is visible even though it sits on the left; below it, 5 is visible too.root = [1,null,3][1,3]1 on the top level, then 3.root = [][]⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 100].-100 <= Node.val <= 100
Core Insight
Level snapshots guarantee that the last element popped at depth d is the rightmost visible node.
Real-World Scenario & Production Applications
3D graphic bounding hull projection, tree shadow rendering.
Step-by-Step Execution Trace Table
Step-by-Step Wavefront Progression
- Step 1 (Root Seed, Depth 0, d=0):
queue = [1]. Initialresult = []. - Step 2 (Snapshot Depth 0, level_size=1, d=0):
level_size = 1. Processing node indexi = 0. - Step 3 (Dequeue 1, Record Silhouette, Depth 0, d=0): Pop
1. Sincei == level_size - 1(last node in depth 0), Record1result = [1]. Enqueue left child2and right child3queue = [2, 3]📸. - Step 4 (Snapshot Depth 1, level_size=2, d=1):
level_size = 2. Processing node indexi = 0.queue = [2, 3]. - Step 5 (Dequeue 2, Intermediate Node, Depth 1, d=1): Pop
2. Sincei = 0 != 1, not rightmost visible. Enqueue right child5queue = [3, 5]. - Step 6 (Dequeue 3, Record Silhouette, Depth 1, d=1): Pop
3. Sincei = 1 == level_size - 1, Record3result = [1, 3]. Enqueue right child4queue = [5, 4]📸. - Step 7 (Snapshot Depth 2, level_size=2, d=2):
level_size = 2. Processing node indexi = 0.queue = [5, 4]. - Step 8 (Dequeue 5, Intermediate Node, Depth 2, d=2): Pop
5. Sincei = 0 != 1, not rightmost visible. Node 5 has no children. - Step 9 (Dequeue 4, Record Silhouette, Depth 2, d=2): Pop
4. Sincei = 1 == level_size - 1, Record4result = [1, 3, 4]. Node 4 has no children 📸. - Step 10 (Queue Empty, Complete, d=2):
queue = []. Right silhouette complete. Search Complete: return[1, 3, 4]✅.
root = [1,2,3,null,5,null,4]Expected:[1,3,4]| 1 | queue = deque([root]) |
| 2 | visible = [] |
| 3 | while queue: |
| 4 | level_size = len(queue) |
| 5 | for i in range(level_size): |
| 6 | node = queue.popleft() |
| 7 | if i == level_size - 1: |
| 8 | visible.append(node.val) |
| 9 | append the children of node to queue |
| 10 | return visible |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Imagine standing on the right side of a binary tree looking inward horizontally. At every vertical level , you can only see exactly one node: the rightmost node at that depth. A common blunder is assuming you can simply follow root.right all the way down. If the right subtree terminates early at depth 2 while the left subtree extends down to depth 10, the left subtree's deeper nodes are completely exposed to the right side! Breadth-First Search solves this effortlessly: traverse the tree level-by-level from left to right, and simply sample the final node popped in each level's snapshot loop.
🏟️ The Analogy: Watching a City Skyline from Across the River
Imagine standing on the eastern bank of a river looking at skyscrapers arranged in east-west rows. For each east-west block, the tallest building furthest to the east is the only one visible on the skyline; any shorter buildings behind it are blocked from view. If a block has no tall buildings on the east end, a building on the west end becomes visible. To draw the skyline silhouette, you look along each row from left to right and record the very last building your eyes land on.
🔑 Why It Works
Because the inner loop runs from i = 0 to level_size - 1, the condition i == level_size - 1 is guaranteed to trigger exactly once per level on the rightmost node, automatically capturing deep left-subtree nodes whenever the right subtree is missing.
Selecting the first element instead of last: The rightmost node is the last element processed in a left-to-right level traversal (
level[-1]), or the first in a right-to-left traversal.Assuming right children shadow all left children: If the right subtree is shallower than the left subtree, lower nodes from the left subtree become visible from the right side. Purely following
.rightpointers fails.Storing all level nodes in memory: Storing the full 2D level array when only the final element of each level is needed wastes auxiliary memory.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Collect rightmost silhouette nodes at each depth level.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: the last node processed in a level-order batch of size N is the rightmost node at that depth.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Assuming the right subtree always contains the rightmost node (a deep left child can be visible if right subtree is shallow).
Using DFS without tracking depth levels visited.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use level-order BFS with queue size snapshots. For each level, I iterate through all nodes at that depth; when i == level_size - 1, I append the node value to my visible list. Runs in
O(N)time andO(N)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: BFS traverses each level, taking the last node in each level queue batch and adding it to the result. Total N nodes.
O(W) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Queue holds max width W nodes.
T(N) = O(N)
Derivation Progression
level_size = len(Q)
Batches each depth tier.
if i == level_size - 1: res.append(val)
Extracts the rightmost visible node in O(1).
N nodes = O(N)
Traverses tree in linear time.
Variable Definitions
Total number of nodes in the binary tree
Maximum level width (at most ⌈N/2⌉ nodes)
Tree height (length of output list)
Memory Architecture & Bounds
O(1) Iterative
O(W) BFS queue
O(H) Result array of size equal to tree height
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "right side view", "visible nodes from top to bottom". Silhouette extraction: you can see exactly one node per depth tier. In a standard level-order BFS, the rightmost visible node is the last node processed in that tier ().
. Time budget linear time.
Empty tree root returns []. Skewed left branches that are deeper than right branches: BFS naturally captures them because once the right branch terminates, the left branch becomes the rightmost survivor at deeper levels.