NeetCode #425LC-199MediumTreesNC 150NC 250
← Back to All Problems#425 · #199 · Binary Tree Right Side View(二叉树的右视图)
📌 Problem Statement & Constraints
Given the root of a binary tree, imagine standing on the right side of it and return the values of the nodes visible from top to bottom. Constraints: the number of nodes is in
[0, 100].💡 Core Algorithmic Approaches
- This is a level-order traversal where only the last node of each level is recorded.
- BFS with a frozen level size makes this trivial: the node at index
n - 1is the rightmost. - A DFS that visits the right child first and records the first node seen at each new depth is an equally valid approach.
- Both are O(n).
💻 Benchmark Python3 Implementation
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
from collections import deque
if not root:
return []
res = []
q = deque([root])
while q:
n = len(q)
for i in range(n):
node = q.popleft()
if i == n - 1: # the rightmost node of this level
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
# DFS variant: right child first, record the first node at each new depth
class Solution2:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node: Optional[TreeNode], depth: int) -> None:
if not node:
return
if depth == len(res): # first node seen at this depth
res.append(node.val)
dfs(node.right, depth + 1) # right first -> rightmost wins
dfs(node.left, depth + 1)
dfs(root, 0)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): every node is visited once.
💾 Space Complexity
O(w) for the BFS queue, or O(h) for the DFS recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Taking the first node of each level in BFS: that is the left view; the right view needs the last node.
- Visiting the left child first in the DFS variant: the leftmost node would be recorded instead.
- Using
depth == len(res)as the condition: this works precisely because the right child is explored first. - Forgetting the empty-tree case: an empty tree has an empty view.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.