Trees — Frame by Frame¶
একটা tree, চারটা walk। প্রতিবার একই ছয়টা node; বদলায় শুধু visit করার মুহূর্তটা। নম্বরগুলো কোথায় পড়ে দেখো।
Tree-টা (এটা একটা BST — inorder-এর জন্য সেটা জরুরি হবে):
একটা traversal প্রতিটা node-কে একবার করে ছোঁয়। Depth-first trio (inorder, preorder, postorder) তিনটাই একই route-এ হাঁটে — বাঁ দিয়ে নামো, উঠে এসো, ডান দিয়ে নামো — পার্থক্য শুধু কখন একটা node তার value চেঁচিয়ে বলে: child-দের আগে, মাঝে, না পরে।
Walk 1: Inorder (Left → Node → Right)¶
"আমাকে visit করো আমার দুই subtree-র মাঝখানে।"
8 ④
/ \
3 ② 10 ⑤
/ \ \
1 ① 6 ③ 14 ⑥ circled = visit order
Output: 1, 3, 6, 8, 10, 14 ← SORTED! (because it's a BST)
ধাপে ধাপে:
at 8: left first ──► at 3: left first ──► at 1: no left → VISIT 1 → no right
back at 3: left done → VISIT 3 → go right ──► at 6: VISIT 6
back at 8: left done → VISIT 8 → go right ──► at 10: no left → VISIT 10
go right ──► at 14: VISIT 14. Done.
BST-তে inorder tree-টাকে toothpaste-এর মতো বাঁ-থেকে-ডানে চিপে বের করে — ছোট থেকে বড়। এই সমীকরণটা (BST + inorder = sorted) এমন একটা tool যা তুমি বারবার ব্যবহার করবে।
Walk 2: Preorder (Node → Left → Right)¶
"আমাকে visit করো সবার আগে, তারপর আমার child-দের।"
Parent সবসময় তার descendant-দের আগে print হয়। Output-টা পড়ে তুমি tree-টা top-down আবার বানাতে পারো: 8 হলো root, তারপর 3 দিয়ে বাঁ দিক শুরু... এই কারণেই preorder হলো serialization/copying-এর order।
Walk 3: Postorder (Left → Right → Node)¶
"আমাকে visit করো সবার শেষে, আমার দুই child পুরোপুরি শেষ হওয়ার পর।"
Child-রা সবসময় parent-দের আগে শেষ করে; root আসে একদম শেষে। "আমার নিজেরটা compute করার আগে আমার child-দের উত্তর লাগবে" — এই কাজের order এটাই — height, subtree sum — আর নিরাপদ deletion-এরও (folder-টা সরানোর আগে folder-টা খালি করো)।
Side-by-side: একই route, তিনটা চেঁচানোর-মুহূর্ত¶
inorder preorder postorder
node 8 4th 1st 6th (last)
node 3 2nd 2nd 3rd
node 1 1st 3rd 1st
node 6 3rd 4th 2nd
node 10 5th 5th 5th
node 14 6th 6th 4th
হাঁটার সময় প্রতিটা node-কে তিনবার "পার" হওয়া হয় (পৌঁছানোর সময়, child-দের মাঝে, ছেড়ে যাওয়ার সময়)। Traversal-এর নাম শুধু ঠিক করে কোন pass-টা গোনা হবে।
Walk 4: Level order (উপর থেকে নিচে, বাঁ থেকে ডানে) — recursion না, queue¶
Breadth-first: পরের layer শুরুর আগে পুরো একটা layer শেষ করো। Engine-টা একটা queue (../04-stack-and-queue/)।
Queue-র movie (front বাঁ দিকে):
frame 0: queue = [8]
frame 1: pop 8, visit it, push children queue = [3, 10]
frame 2: pop 3, visit, push 1, 6 queue = [10, 1, 6]
frame 3: pop 10, visit, push 14 queue = [1, 6, 14]
frame 4: pop 1, visit (leaf, nothing pushed) queue = [6, 14]
frame 5: pop 6, visit queue = [14]
frame 6: pop 14, visit queue = [] → done
FIFO queue-টাই পুরো কায়দা: child-রা পেছনে যোগ দেয়, তাই level k-র প্রতিটা node খালি হয়ে যায় level k+1-এর কোনো node ভেসে ওঠার আগেই। এখানে একটা stack (LIFO) বসাও আর তুমি depth-first ডুব দিতে — DFS/BFS-এর পুরো পার্থক্যটাই এই একটা data-structure-এর পছন্দে।
Bonus frame: bottom-up height হিসাব (postorder কাজে নেমেছে)¶
একই tree-তে উত্তরগুলো উপরে উঠতে দেখো (empty-র height = -1):
8 = 1 + max(1, 1) = 2 ← computed LAST
/ \
1+max(0,0)=1 1+max(-1,0)=1
/ \ \
0 0 0 ← leaves resolve first
প্রতিটা parent তার দুই child-এর সংখ্যার জন্য অপেক্ষা করে — যেটা ঠিক postorder-এর visit-মুহূর্ত। কোনো tree problem যখনই বলে "child-দের result জোড়া লাগাও", তোমার মাথায় বাজা উচিত "postorder"।
এই frame-গুলো থেকে যা মনে রাখবে¶
- DFS trio: একটা route, তিনটা চেঁচানোর-মুহূর্ত। In = মাঝে, Pre = আগে, Post = পরে।
- BST + inorder = sorted output। এটা পুড়িয়ে মাথায় গেঁথে নাও।
- Preorder বানায় top-down; postorder হিসাব করে bottom-up।
- Level order = queue। Queue দেয় layer; stack দিত depth।
পরের file: traversal-patterns.md — কখন কোন walk-টা সঠিক tool, plus বড় tree problem pattern-গুলো।