MediumNeetCode150TreeDepth-First SearchBreadth-First SearchBinary Tree
Binary Tree Right Side View
Return values visible from right side.
Examples
Input
root = [1,2,3,null,5,null,4]
Output
[1,3,4]
From right: 1, 3, 4.
Constraints
- •
Number of nodes in [0,100] - •
-100 <= Node.val <= 100
Approaches
Take last node per level.
CodeT: O(n) | S: O(n)
from collections import deque
def rightSideView(root):
if not root: return []
r=[]; q=deque([root])
while q:
ls=len(q)
for i in range(ls):
n=q.popleft()
if i==ls-1: r.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
return rVisit right child first.
CodeT: O(n) | S: O(h)
def rightSideView(root):
r=[]
def dfs(n,d):
if not n: return
if d==len(r): r.append(n.val)
dfs(n.right,d+1); dfs(n.left,d+1)
dfs(root,0); return rSame approach.
CodeT: O(n) | S: O(h)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| BFS Level Order | O(n) | O(n) | Take last node per level. |
| DFS Right First | O(n) | O(h) | Visit right child first. |
| DFS Right Priority | O(n) | O(h) | Same approach. |
BFS Level Order
T: O(n)S: O(n)
Take last node per level.
DFS Right First
T: O(n)S: O(h)
Visit right child first.
DFS Right Priority
T: O(n)S: O(h)
Same approach.
Common Mistakes
Taking first node instead of last
Not handling null root
Visiting left before right