এই নোটে ট্রি ট্র্যাভার্সাল একদম শুরু থেকে শেখানো হয়েছে — কোনো ধাপ বাদ না দিয়ে, প্রতিটি ধাপের পেছনের কারণসহ। শেষে খাতায় লেখার মতো এক্স্যাক্ট Exam Answer দেওয়া আছে।
প্রশ্ন (যেভাবে পরীক্ষায় আসে):
Given the following binary tree, write down its Preorder, Inorder, Postorder, and Level order traversal. Also define Root, Leaf, Height, Depth, Full, Complete, and Perfect binary tree, with the maximum-node formulas.
Tree হলো একটা hierarchical (স্তরবিন্যাস করা) ডেটা স্ট্রাকচার — অনেকটা পারিবারিক বংশতালিকার মতো। একদম উপরে একটা Root (মূল) node থাকে, আর তার নিচে ধাপে ধাপে Children (সন্তান) node গুলো ছড়িয়ে থাকে। Tree-তে কোনো cycle (চক্র) থাকে না — মানে কোনো node থেকে ঘুরে আবার সেই node-এ ফিরে আসার রাস্তা নেই।
যে Tree-এর প্রতিটা node-এর সর্বোচ্চ দুইটা child থাকতে পারে — একটা Left child আর একটা Right child — তাকে বলে Binary Tree। "Binary" শব্দটাই বলে দিচ্ছে দুই সংখ্যক সম্ভাবনা: বাম আর ডান।
| টার্ম | মানে (বাংলায়) | কেন জানা দরকার |
|---|---|---|
| Node | ট্রি-এর প্রতিটা বক্স/উপাদান, যাতে একটা value থাকে | Traversal মানেই প্রতিটা node visit করা — তাই node কী বুঝতে হবে |
| Root | সবচেয়ে উপরের node, যার কোনো parent নেই | প্রতিটা traversal-এর সংজ্ঞাই Root-এর position দিয়ে আলাদা হয় |
| Leaf | যে node-এর কোনো child নেই | Recursion কোথায় থামবে (base case) সেটা Leaf দিয়েই বোঝা যায় |
| Parent / Child | উপরের node parent, নিচের node child | ট্রি-এর সম্পর্ক বোঝাতে দরকার |
| Subtree | যেকোনো node-কে root ধরে তার নিচের পুরো অংশ | Traversal-এর সবচেয়ে জরুরি কৌশল — subtree ভাগ করেই সমাধান করা হয় |
| Height | Root থেকে সবচেয়ে গভীর leaf পর্যন্ত edge-এর সংখ্যা | Complexity ও max-node formula-তে লাগে |
| Depth | Root থেকে নির্দিষ্ট একটা node পর্যন্ত edge-এর সংখ্যা | Level বের করতে লাগে |
Tree-এর প্রতিটা data linear (সিরিয়াল) না — array বা list-এর মতো এক লাইনে নেই। তাই সব node-কে একটা নির্দিষ্ট নিয়মে "ভ্রমণ" (traverse) করে visit করার পদ্ধতিই হলো Traversal। এক্সপ্রেশন evaluate করা, ফাইল সিস্টেম দেখানো, সার্চ করা — সব জায়গায় Traversal লাগে।
Tree Traversal is the process of visiting every node of a tree exactly once in a systematic manner.
একটা জিনিস মনে রাখলেই তিনটা traversal মুখস্থ হয়ে যাবে — "Root কোথায় বসছে?"
| Traversal | Order | Root-এর position |
|---|---|---|
| Preorder | Root → Left → Right | সবার প্রথমে |
| Inorder | Left → Root → Right | মাঝে |
| Postorder | Left → Right → Root | সবার শেষে |
| Level order | Level অনুযায়ী উপর থেকে নিচে, প্রতি লেভেলে বাম থেকে ডানে (BFS) | |
প্রতিটা subtree নিজেই একটা ছোট ট্রি — তারও একটা root, left, right আছে। তাই একই নিয়ম (Root/Left/Right-এর অর্ডার) প্রতিটা subtree-তে বারবার প্রয়োগ করলেই পুরো ট্রি traverse হয়ে যায়। এটাই Recursion-এর মূল ধারণা: বড় সমস্যাকে ছোট, একই-রকম সমস্যায় ভাঙা।
// Preorder: Root → Left → Right
Preorder(node):
if node is NULL: return
visit(node) // Root first
Preorder(node.left) // then Left
Preorder(node.right) // then Right
// Inorder: Left → Root → Right
Inorder(node):
if node is NULL: return
Inorder(node.left) // Left first
visit(node) // then Root
Inorder(node.right) // then Right
// Postorder: Left → Right → Root
Postorder(node):
if node is NULL: return
Postorder(node.left) // Left first
Postorder(node.right) // then Right
visit(node) // Root last
// Level Order: BFS with a queue
LevelOrder(root):
if root is NULL: return
queue.enqueue(root)
while queue is not empty:
node = queue.dequeue()
visit(node)
if node.left != NULL: queue.enqueue(node.left)
if node.right != NULL: queue.enqueue(node.right)if node is NULL: returnকী হচ্ছে: ফাংশনটা প্রথমেই দেখে node-টা আসলে আছে কি না।
কেন দরকার: এটা না থাকলে Recursion কখনো থামবে না — Leaf-এর নিচেও (যেটা NULL) আবার call হতে যাবে এবং প্রোগ্রাম ক্র্যাশ করবে। এটাই Recursion-এর "থামার শর্ত"।
কী হচ্ছে: Preorder-এ আগে Root visit হয়, তারপর নিজেকে (একই ফাংশন) Left child দিয়ে আবার call করে, তারপর Right child দিয়ে call করে।
কেন দরকার: Left subtree-টা যতক্ষণ না পুরোপুরি শেষ হচ্ছে, ততক্ষণ Right subtree-তে যাওয়া হয় না — এটাই নিশ্চিত করে বাম দিকের সব node আগে আসবে।
কী হচ্ছে: Root প্রথমে queue-তে ঢোকে। তারপর queue থেকে একটা node বের করে visit করে, তার left ও right child থাকলে queue-তে ঢুকিয়ে দেয়। এটা চলতেই থাকে যতক্ষণ queue খালি না হয়।
কেন Queue (Stack না): Queue হলো FIFO (First In, First Out) — যেটা আগে ঢুকেছে সেটাই আগে বের হয়। এতে করে উপরের level আগে শেষ হয়ে তারপর নিচের level শুরু হয় — মানে "level-by-level" আচরণটা স্বাভাবিকভাবেই তৈরি হয়।
A
/ \
B C
/ \ \
D E FC-এর শুধু ডান পাশে child F আছে — বাম দিক খালি। এই জিনিসটা মিস করলেই ভুল উত্তর হবে। ছবি না দেখে অনুমান করে বসলে এখানেই সবচেয়ে বেশি ভুল হয়।
কী করলাম: পুরো ট্রি-টাকে তিন ভাগে ভাগ করলাম — Root, Root-এর Left subtree, আর Root-এর Right subtree।
Root = A
Left subtree of A = { B, D, E } (B root, D বামে, E ডানে)
Right subtree of A = { C, F } (C root, বাম খালি, F ডানে)বড় ট্রি একসাথে মাথায় রেখে traverse করা কঠিন। কিন্তু Root আর তার দুই subtree আলাদা করে ফেললে, প্রতিটা subtree-কে একটা ছোট, স্বাধীন সাব-প্রবলেম হিসেবে সমাধান করা যায় — এটাই Recursion-এর হাতে-কলমে প্রয়োগ।
কী করলাম: আগে Root (A), তারপর পুরো Left subtree-এর preorder (B, D, E), তারপর পুরো Right subtree-এর preorder (C, F) — পাশাপাশি বসিয়ে দিলাম।
ফলাফল: A, B, D, E, C, F
কী করলাম: B-subtree-এর ভেতরে D আগে (B-এর বাম child), তারপর B নিজে, তারপর E (B-এর ডান child) — তাই B-subtree-এর inorder হলো D, B, E। এরপর Root A, তারপর C-subtree-এর inorder (C-এর বাম খালি, তাই C তারপর F) → C, F।
ফলাফল: D, B, E, A, C, F
কী করলাম: B-subtree-এ D, E আগে তারপর B (postorder = D, E, B)। C-subtree-এ বাম খালি, তাই F আগে তারপর C (postorder = F, C)। সবশেষে Root A।
ফলাফল: D, E, B, F, C, A
Preorder: A, B, D, E, C, F
Inorder: D, B, E, A, C, F
Postorder: D, E, B, F, C, A
Level order: A, B, C, D, E, F
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9Root = 1
Left subtree of 1 = { 2, 4, 5, 8 }
Right subtree of 1 = { 3, 6, 7, 9 }Left subtree-এর ভেতরে: 2-এর বাম child 4, ডান child 5; আর 5-এর বাম child 8 (5-এর ডান খালি)।
Right subtree-এর ভেতরে: 3-এর বাম child 6, ডান child 7; আর 7-এর ডান child 9 (7-এর বাম খালি)।
Preorder (Root→Left→Right): 1, তারপর {2,4,5,8}-subtree = 2,4,5,8, তারপর {3,6,7,9}-subtree = 3,6,7,9
Inorder (Left→Root→Right): {4,2,8,5}, তারপর 1, তারপর {6,3,7,9}
Postorder (Left→Right→Root): {4,8,5,2}, তারপর {6,9,7,3}, তারপর 1
Level order (BFS, level ধরে ধরে): Level 1 → 1; Level 2 → 2,3; Level 3 → 4,5,6,7; Level 4 → 8,9
| Traversal | Answer |
|---|---|
| Preorder | 1, 2, 4, 5, 8, 3, 6, 7, 9 |
| Inorder | 4, 2, 8, 5, 1, 6, 3, 7, 9 |
| Postorder | 4, 8, 5, 2, 6, 9, 7, 3, 1 |
| Level order | 1, 2, 3, 4, 5, 6, 7, 8, 9 |
Preorder: 1, 2, 4, 5, 8, 3, 6, 7, 9
Inorder: 4, 2, 8, 5, 1, 6, 3, 7, 9
Postorder: 4, 8, 5, 2, 6, 9, 7, 3, 1
Level order: 1, 2, 3, 4, 5, 6, 7, 8, 9
| টার্ম | সংজ্ঞা |
|---|---|
| Root | সবচেয়ে উপরের node |
| Leaf | যার কোনো child নেই |
| Height of tree | Root থেকে সবচেয়ে গভীর leaf পর্যন্ত edge-এর সংখ্যা |
| Depth of node | Root থেকে সেই node পর্যন্ত edge-এর সংখ্যা |
| Level | Depth + 1 (বই ভেদে সংজ্ঞা আলাদা হতে পারে — খাতায় definition লিখে দিও) |
| Full binary tree | প্রতিটা node-এর 0 বা 2টা child |
| Complete binary tree | শেষ level ছাড়া সব level ভরতি, আর শেষ level বাম থেকে ভরতি |
| Perfect binary tree | সব leaf একই level-এ, সব internal node-এর 2টা child |
L-এ max node = 2^(L−1) (level 1 থেকে শুরু ধরে)h-এর tree-তে max node = 2^(h+1) − 1n node-এর tree-এর min height = ⌊log₂ n⌋