Problem link ও উৎস
- **Original source:** Classic level-order tree traversal variant
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Medium
- **Pattern:** Level order
- **Basic idea inherited from:** Level Order Traversal, প্রতি level-এর শেষটা রাখো (এই tracker-এর #12)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কল্পনা করো তুমি tree-টার **ডান পাশে** দাঁড়িয়ে আছ। প্রতিটা level থেকে তুমি শুধু সেই node-গুলো দেখতে পাবে যেগুলো সবার ডানে — বাকি সব তাদের পেছনে লুকিয়ে। তোমার কাজ: উপর থেকে নিচে, প্রতি level-এর সেই **rightmost node**-এর value ফেরত দেওয়া।
```text
1 ← দেখা যায়: 1
/ \
2 3 ← দেখা যায়: 3 (2 লুকানো)
\ \
5 4 ← দেখা যায়: 4 → উত্তর: [1, 3, 4]
```
### Input ও output {#8-example-input-and-output}
```text
Input : root = [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Input : root = [1,null,3] -> Output: [1, 3]
Edge : root = [] -> Output: [] (খালি tree)
Input : root = [1,2,3,4] -> Output: [1, 3, 4] (level 3-এ একমাত্র node 4)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা parade হচ্ছে, তুমি রাস্তার ডান ধারে দাঁড়িয়ে। প্রতিটা row যখন তোমার সামনে দিয়ে যায়, তুমি শুধু সেই row-এর ডান-প্রান্তের লোকটাকে দেখতে পাও — বাকিরা তার পেছনে। প্রতিটা row (level) থেকে তুমি একজনকেই (rightmost) মনে রাখো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **Level Order Traversal** (#12) থেকে আসে। সেখানে আমরা প্রতি level-এর পুরো list বানাতাম; এখানে শুধু প্রতি level-এর **শেষ** element-টা লাগবে। একই BFS কঙ্কাল, শুধু "পুরো level জমাও"-এর জায়গায় "level-এর শেষটা তুলে রাখো।"
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একই BFS-by-level, একটা ছোট filter সহ:
```text
প্রতিটা level L-এর জন্য:
right_view += [ L-এর শেষ node-এর value ]
```
"শেষ" মানে সেই level-এ বাঁ-থেকে-ডানে process করার সময় index `size - 1`-এ থাকা node। যেহেতু আমরা child enqueue করি left-আগে-right, level-এর শেষ node সবসময় rightmost।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **FIFO queue** (`collections.deque`) — Level Order Traversal-এর মতোই। সাথে একটা output list যেখানে প্রতি level-এর rightmost value যোগ হয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Queue-র FIFO ধর্ম একটা level-কে তার পরের level থেকে আলাদা রাখে। left-আগে-right enqueue করায় প্রতি level-এর শেষ-process-হওয়া node-ই rightmost — তাই `i == size - 1` চেক করলেই সঠিক node পাওয়া যায়, আলাদা কোনো হিসাব ছাড়াই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: পুরো Level Order Traversal চালাই (list-of-lists বানাই), তারপর প্রতিটা inner list-এর শেষ element তুলি।
```text
1) levels = [[1], [2, 3], [5, 4]]
2) প্রতিটা level-এর শেষ: 1, 3, 4
3) উত্তর = [1, 3, 4]
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা ঠিক উত্তর দেয় আর O(n)-ও, কিন্তু প্রতিটা level-এর পুরো list বানিয়ে শুধু শেষ element রাখা — বাকি সব value বানানো ও ফেলে দেওয়া অপচয়। সরাসরি BFS-এর ভেতরেই `i == size - 1` চেক করে শুধু rightmost তুলে নিলে extra list memory বাঁচে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **left-আগে-right enqueue করলে প্রতিটা level-এর শেষ-process-হওয়া node-ই rightmost।** তাই আলাদা করে "ডান দিকের" হিসাব করতে হয় না — শুধু লুপের শেষ iteration (`i == size - 1`)-এর node ধরলেই হলো।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
এটা **level order** traversal, প্রতি level-এ একটাই pick। BFS করো; প্রতি level-এর শুরুতে `size = len(q)`; লুপের সময় যখন `i == size - 1`, সেই node-এর value output-এ দাও। প্রতিটা node একবার দেখা হয় — O(n), কিন্তু per-level list না বানিয়ে।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "ডান দিকের সব node খুঁজব" ভাবা বন্ধ করো — সেটা ভুল পথ (একটা node বাঁ subtree-তে থেকেও rightmost-visible হতে পারে যদি ডান subtree খাটো হয়)। বরং ভাবো "প্রতি level-এ সবার শেষে যাকে দেখব, সে-ই উত্তর।" Level-ভিত্তিক চিন্তা problem-টাকে এক-লাইন filter বানিয়ে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতি wave-এ queue-র শেষ-process-হওয়া node-টাই দৃশ্যমান:
```text
queue: [1] size=1 → শেষ index 0 → দেখা যায় 1
queue: [2, 3] size=2 → শেষ index 1 → দেখা যায় 3
queue: [5, 4] size=2 → শেষ index 1 → দেখা যায় 4
right view = [1, 3, 4]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[1,2,3,null,5,null,4]`:
1. `q = [1]`। `size = 1`। i=0 → শেষ (0 == 0), 1 যোগ করো। enqueue 2, 3। `q = [2, 3]`।
2. `size = 2`। i=0 → 2 (শেষ না), enqueue 5। i=1 → 3 শেষ, 3 যোগ করো, enqueue 4। `q = [5, 4]`।
3. `size = 2`। i=0 → 5 (শেষ না)। i=1 → 4 শেষ, 4 যোগ করো। কারো child নেই। `q = []`।
4. শেষ। `result = [1, 3, 4]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(values):
"""level-order list (None = missing child) থেকে tree বানায়।"""
if not values:
return None
root = TreeNode(values[0])
q = deque([root])
i = 1
while q and i < len(values):
node = q.popleft()
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
q.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
q.append(node.right)
i += 1
return root
def right_side_view(root):
if root is None: # খালি tree: কিছু দেখা যায় না
return []
view, q = [], deque([root]) # BFS queue (../../04-stack-and-queue/)
while q:
size = len(q) # এই snapshot = ঠিক একটা level
for i in range(size):
node = q.popleft()
if i == size - 1: # level-এর শেষ = rightmost
view.append(node.val)
if node.left:
q.append(node.left) # left আগে enqueue
if node.right:
q.append(node.right) # তারপর right
return view
# ---- tests ----
assert right_side_view(build_tree([1, 2, 3, None, 5, None, 4])) == [1, 3, 4]
assert right_side_view(build_tree([1, None, 3])) == [1, 3]
assert right_side_view(build_tree([])) == []
assert right_side_view(build_tree([1, 2, 3, 4])) == [1, 3, 4]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if root is None: return []` — খালি tree-তে কিছু দেখা যায় না।
- `view, q = [], deque([root])` — output আর BFS queue।
- `size = len(q)` — বর্তমান level-এর সীমানা।
- `for i in range(size)` — index সহ লুপ, যাতে শেষ iteration চেনা যায়।
- `if i == size - 1: view.append(node.val)` — level-এর শেষ-process-হওয়া node-ই rightmost।
- `if node.left: q.append(...)` আগে, তারপর `right` — এই order-ই শেষ node-কে rightmost বানায়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build_tree([1,2,3,None,5,None,4])` ওই ছবির tree বানায়; `right_side_view` `[1, 3, 4]` ফেরত দেয় — assert pass। একপাশে-ঝোলা `[1,null,3]` দেয় `[1, 3]`, খালি tree দেয় `[]`, আর `[1,2,3,4]` দেয় `[1, 3, 4]` (level 3-এ rightmost আসলে বাঁ subtree-র 4) — সব pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা node ঠিক একবার enqueue/dequeue হয় (n = node সংখ্যা)। শুধু একটা সরল index-চেক যোগ হয়েছে, যা O(1)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — queue-তে সবচেয়ে বেশি একটা পুরো level (চওড়া tree-তে প্রায় n/2 node)। Output সবচেয়ে বেশি height-সমান লম্বা, যা O(n)-এর মধ্যে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- "rightmost মানে শুধু ডান subtree" ধরে নিয়ে `node.right` থাকলেই কেবল নামা → বাঁ subtree গভীর হলে নিচের level-এর visible node মিস হয়।
- `size = len(q)` snapshot ভুলে যাওয়া → level-এর সীমানা হারায়, ভুল node "শেষ" হিসেবে ধরা পড়ে।
- left-এর আগে right enqueue করা → তখন "শেষ" node leftmost হয়ে যায়, উত্তর উল্টে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Level Order Traversal (#12)-এর BFS কঙ্কাল আর `size = len(q)` snapshot। শুধু "পুরো level জমাও"-এর জায়গায় "level-এর শেষটা তোলো" — এটুকুই পার্থক্য।
### পরের অনুশীলন {#22-similar-harder-problems}
- Binary Tree Left Side View (একই কায়দা, `i == 0` চেক) —