013 — Binary Tree Right Side View¶
Source¶
- Original source: Classic level-order tree traversal variant
- Platform: LeetCode — https://leetcode.com/problems/binary-tree-right-side-view/
- Topic: trees
- Difficulty: Medium
- Pattern: Level order
- Basic idea inherited from: Level Order Traversal, প্রতি level-এর শেষটা রাখো (এই tracker-এর #12)
1. Problem in simple words¶
কল্পনা করো তুমি tree-টার ডান পাশে দাঁড়িয়ে আছ। প্রতিটা level থেকে তুমি শুধু সেই node-গুলো দেখতে পাবে যেগুলো সবার ডানে — বাকি সব তাদের পেছনে লুকিয়ে। তোমার কাজ: উপর থেকে নিচে, প্রতি level-এর সেই rightmost node-এর value ফেরত দেওয়া।
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 সহ:
"শেষ" মানে সেই 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 পাওয়া যায়, আলাদা কোনো হিসাব ছাড়াই।
6. Real-life analogy¶
একটা parade হচ্ছে, তুমি রাস্তার ডান ধারে দাঁড়িয়ে। প্রতিটা row যখন তোমার সামনে দিয়ে যায়, তুমি শুধু সেই row-এর ডান-প্রান্তের লোকটাকে দেখতে পাও — বাকিরা তার পেছনে। প্রতিটা row (level) থেকে তুমি একজনকেই (rightmost) মনে রাখো।
7. Visual explanation¶
প্রতি wave-এ queue-র শেষ-process-হওয়া node-টাই দৃশ্যমান:
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]
8. Example input and output¶
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)
9. Brute force thinking¶
প্রথম সরল চিন্তা: পুরো Level Order Traversal চালাই (list-of-lists বানাই), তারপর প্রতিটা inner list-এর শেষ element তুলি।
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 বানিয়ে দেয়।
14. Step-by-step dry run¶
Input [1,2,3,null,5,null,4]:
q = [1]।size = 1। i=0 → শেষ (0 == 0), 1 যোগ করো। enqueue 2, 3।q = [2, 3]।size = 2। i=0 → 2 (শেষ না), enqueue 5। i=1 → 3 শেষ, 3 যোগ করো, enqueue 4।q = [5, 4]।size = 2। i=0 → 5 (শেষ না)। i=1 → 4 শেষ, 4 যোগ করো। কারো child নেই।q = []।- শেষ।
result = [1, 3, 4]।
15. Python solution¶
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 বানায়।
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!।
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 হয়ে যায়, উত্তর উল্টে যায়।
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চেক) — https://leetcode.com/problems/binary-tree-right-side-view/ (mirror বানিয়ে) - Find Largest Value in Each Tree Row (প্রতি level-এর max) — https://leetcode.com/problems/find-largest-value-in-each-tree-row/
- Binary Tree Level Order Traversal II (নিচ থেকে উপরে level order) — https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
23. Pattern learned¶
Per-level pick: level order BFS চালাও, কিন্তু প্রতি level থেকে পুরো list না নিয়ে একটা বিশেষ element তোলো (শেষটা, প্রথমটা, max, গড়)। Right side view হলো "শেষটা নাও" রূপ; এই কাঠামোয় filter বদলালেই অনেক per-level problem সমাধান হয়।
24. Final summary¶
ভবিষ্যতের আমাকে: "right side view = level order BFS + প্রতি level-এর শেষ node।" left-আগে-right enqueue করলে i == size - 1-ই rightmost। যখনই 'প্রতি level থেকে একটা জিনিস' টাইপ problem দেখবে, এই Level Order-এর উপর filter বসানোর কথা মনে করবে।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।