Topic 06 · Binary Tree
Traversal থেকে Binary Tree তৈরি
Traversal থেকে গাছ আঁকার প্রশ্ন — উল্টো দিকের কাজ। মূল চাবিকাঠি একটাই:
Inorder বলে দেয় কে বামে কে ডানে, আর Pre/Post বলে দেয় কে root।
১. প্রশ্ন (Question)
EXAM QUESTION
(a) Preorder = A B D E C F G এবং Inorder = D B E A F C G —
binary tree টি আঁকো এবং তার Postorder লেখো।
(b) Postorder = D E B F C A এবং Inorder = D B E A F C —
binary tree টি আঁকো এবং তার Preorder লেখো।
(c) শুধু Preorder ও Postorder দিয়ে কি unique binary tree তৈরি করা যায়?
উদাহরণসহ ব্যাখ্যা করো।
২. Prerequisite Concepts (আগে যা জানা দরকার)
২.১ তিনটা Traversal — root কোথায় থাকে
এই টপিকের পুরোটাই এই এক টেবিলের উপর দাঁড়ানো:
| Traversal | ক্রম | Root কোথায় |
|---|
| Preorder | Root → Left → Right | সবার প্রথমে |
| Inorder | Left → Root → Right | মাঝখানে |
| Postorder | Left → Right → Root | সবার শেষে |
কেন দরকার: Preorder এর প্রথম অক্ষর বা Postorder এর শেষ অক্ষর — এটাই root।
এই এক তথ্য দিয়েই পুরো গাছ খুলে ফেলা যায়।
২.২ Inorder এর বিশেষ ক্ষমতা
Inorder এ root এর বাম পাশে যা কিছু আছে, তার সবটাই root এর left subtree।
আর ডান পাশে যা আছে, তার সবটাই right subtree।
কেন দরকার: Preorder/Postorder শুধু বলে "কে root", কিন্তু বলে না "কে বামে কে ডানে"।
Inorder ছাড়া গাছ দুই ভাগে ভাগ করাই যায় না। তাই Inorder সবসময় লাগবেই — এটাই
এই টপিকের এক নম্বর নিয়ম।
২.৩ Subtree কী?
কোনো node এবং তার নিচের সব node মিলে যে অংশ, সেটাই ওই node এর subtree।
একটা subtree নিজেও একটা সম্পূর্ণ binary tree।
কেন দরকার: আমরা পুরো গাছটা একবারে বানাই না — root বের করে দুইটা ছোট subtree তে ভাগ করি,
তারপর প্রতিটা subtree এর জন্য একই কাজ আবার করি। এটাই recursion।
২.৪ Unique Tree — শর্ত কী
| যা দেওয়া আছে | Unique tree হবে? | Root পাবো কোথায় |
|---|
| Preorder + Inorder | হ্যাঁ ✓ | Preorder এর প্রথম |
| Postorder + Inorder | হ্যাঁ ✓ | Postorder এর শেষ |
| Preorder + Postorder | না ✗ | (unique নয়) |
| Level order + Inorder | হ্যাঁ ✓ | Level order এর প্রথম |
| যেকোনো একটা মাত্র traversal | না ✗ | — |
মনে রাখার সহজ সূত্র: "Inorder থাকলে unique, না থাকলে নয়।"
৩. Exam Definition (English)
Tree Construction from Traversals: Given the inorder traversal together with either the
preorder or the postorder traversal of a binary tree, the tree can be reconstructed uniquely.
The first element of the preorder (or the last element of the postorder) identifies the root.
Locating that root inside the inorder sequence splits the remaining elements into the left
subtree (all elements before the root) and the right subtree (all elements after the root).
The same procedure is then applied recursively to each subtree. The time complexity is
O(n²) in the naive form and O(n) when a hash map is used to locate the
root in the inorder sequence.
Note: Preorder together with postorder does not uniquely determine a general
binary tree, because neither sequence indicates whether a single child is a left child or a
right child.
৪. Concept Explanation (বাংলায়)
ভাবো তুমি একটা গাছ ভেঙে তিনভাবে লাইনে সাজিয়ে দিয়েছ। এখন লাইন দেখে আবার গাছটা
বানাতে হবে। দুইটা তথ্য লাগবে —
১। কে root? — এটা Preorder এর প্রথম অক্ষর বলে দেয় (কারণ preorder এ root আগে আসে)।
অথবা Postorder এর শেষ অক্ষর (কারণ postorder এ root শেষে আসে)।
২। বাকিরা কে বামে, কে ডানে? — এটা Inorder বলে দেয়। Inorder এ root খুঁজে বের করে
কাটলে বামের অংশটা left subtree, ডানের অংশটা right subtree।
এই দুইটা তথ্য পাওয়ার পর কাজটা ছোট হয়ে যায় — এখন left subtree এর জন্য একই কাজ,
right subtree এর জন্য একই কাজ। যতক্ষণ না প্রতিটা অংশে একটা মাত্র node থাকে, ততক্ষণ
চলতে থাকে। একেই বলে divide and conquer।
৫. Algorithm (English)
BUILD_TREE(preorder, inorder)
if inorder is empty then
return NULL
root_value = preorder[0] // first of preorder = root
root = new Node(root_value)
k = index of root_value in inorder // split point
left_inorder = inorder[0 .. k-1] // everything before root
right_inorder = inorder[k+1 .. end] // everything after root
left_preorder = preorder[1 .. k] // next k elements
right_preorder = preorder[k+1 .. end] // the rest
root.left = BUILD_TREE(left_preorder, left_inorder)
root.right = BUILD_TREE(right_preorder, right_inorder)
return root
Postorder এর ক্ষেত্রে শুধু দুইটা লাইন বদলায়:
• root_value = postorder[last] — প্রথমের বদলে শেষ
• left_postorder = postorder[0 .. k-1], right_postorder = postorder[k .. last-1]
৬. ধাপে ধাপে ব্যাখ্যা (বাংলায়)
ধাপ ১ — Root চিনে নাও
Preorder দেওয়া থাকলে
প্রথম element, Postorder দেওয়া থাকলে
শেষ element।
কেন: সংজ্ঞা অনুযায়ীই preorder এ root আগে ছাপা হয় আর postorder এ পরে।
ধাপ ২ — Inorder এ root খুঁজে দাগ টানো
Root এর বামের সব element = left subtree, ডানের সব = right subtree।
কেন: Inorder এর ক্রম হলো Left → Root → Right, তাই root এর অবস্থানই স্বাভাবিকভাবে দুই ভাগ করে দেয়।
ধাপ ৩ — Element গুনে Pre/Post ও ভাগ করো
Left subtree তে যদি k টা element থাকে, তাহলে preorder এর root এর পরের
ঠিক k টা
element হলো left subtree এর preorder; বাকিটা right subtree এর।
কেন গুনতে হবে: এই গোনাটাই সবচেয়ে বেশি ভুল হয়। সংখ্যা না মিললে গাছ ভুল হবেই।
তাই প্রতিটা ধাপে "বামে কয়টা, ডানে কয়টা" লিখে রাখো।
ধাপ ৪ — প্রতিটা অংশে একই কাজ আবার করো
Left অংশের জন্য ধাপ ১–৩, Right অংশের জন্য ধাপ ১–৩। একটা element বাকি থাকলে সেটাই leaf।
কেন: subtree ও একটা সম্পূর্ণ tree, তাই একই নিয়ম খাটে — এটাই recursion।
ধাপ ৫ — গাছ এঁকে যাচাই করো
আঁকা গাছ থেকে আবার Inorder বের করো — দেওয়া Inorder এর সাথে হুবহু মিললে গাছ ঠিক আছে।
কেন দরকার: এক লাইনের যাচাই, কিন্তু ভুল ধরে ফেলে। খাতায় এই লাইনটার জন্য নম্বর আছে।
৭. Q1 সমাধান — Preorder + Inorder
Preorder = A B D E C F G (root সবার আগে)
Inorder = D B E A F C G (root মাঝখানে)
Step 1 — Root = A (preorder এর প্রথম)
Inorder এ A খুঁজে দাগ টানি:
D B E | A | F C G
←── বাম ──┘ root └── ডান ──→
Left subtree = { D, B, E } → 3 টা element
Right subtree = { F, C, G } → 3 টা element
Step 2 — Preorder কে একই অনুপাতে ভাগ করি
Preorder = A | B D E | C F G
↑ └─ ৩টা ─┘ └─ ৩টা ─┘
root বামের ডানের
কী করলাম: A এর পরের ঠিক ৩টা element (B, D, E) নিলাম left subtree এর preorder হিসেবে।
কেন ৩টা: কারণ inorder এ বাম পাশে ঠিক ৩টা element ছিল। সংখ্যা অবশ্যই মিলতে হবে।
Step 3 — পুরো ভাঙা টেবিল আকারে
Step 4 — গাছ
A
/ \
B C
/ \ / \
D E F G
Step 5 — যাচাই ও Postorder
যাচাই — গাছ থেকে Inorder: D , B , E , A , F , C , G ✓ (দেওয়াটার সাথে হুবহু মিলে গেছে)
Postorder = Left → Right → Root
= [ D , E , B ] + [ F , G , C ] + A
Postorder = D, E, B, F, G, C, A
যাচাই: Inorder মিলে গেছে ✓ · প্রতিটা subtree এ element সংখ্যা মিলেছে ✓
৮. Q2 সমাধান — Postorder + Inorder
Postorder = D E B F C A (root সবার শেষে)
Inorder = D B E A F C (root মাঝখানে)
Step 1 — Root = A (postorder এর শেষ)
Inorder এ A খুঁজে দাগ টানি:
D B E | A | F C
←── বাম ──┘ root └─ ডান ─→
Left subtree = { D, B, E } → 3 টা
Right subtree = { F, C } → 2 টা
Step 2 — Postorder ভাগ করি (শেষেরটা বাদ দিয়ে)
Postorder = D E B | F C | A
└─ ৩টা ─┘└২টা┘ ↑
বামের ডানের root
কী করলাম: শেষের A বাদ দিয়ে সামনের ঠিক ৩টা (D, E, B) নিলাম বামের জন্য, পরের ২টা
(F, C) ডানের জন্য। কেন এই ক্রমে: postorder এর ক্রম হলো Left → Right → Root,
তাই বামের অংশ আগে, তারপর ডানের, শেষে root।
Step 3 — পুরো ভাঙা টেবিল আকারে
সবচেয়ে গুরুত্বপূর্ণ জায়গা — Right subtree: Inorder এ F C, অর্থাৎ
root C এর বাম পাশে F আছে, ডান পাশে কিছু নেই। তাই F হলো C এর left child,
আর C এর right child খালি। এখানেই সবচেয়ে বেশি ভুল হয় — অনেকে F কে ডানে বসিয়ে দেয়।
Step 4 — গাছ
A
/ \
B C
/ \ /
D E F
Step 5 — যাচাই ও Preorder
যাচাই — গাছ থেকে Inorder: D , B , E , A , F , C ✓
Preorder = Root → Left → Right
= A + [ B , D , E ] + [ C , F ]
Preorder = A, B, D, E, C, F
C এর কোনো right child নেই — F তার left child
৯. Q3 — Preorder + Postorder দিয়ে unique tree হয় না
ধরা যাক Preorder = A B C এবং Postorder = C B A।
এই দুইটার সাথে চারটা আলাদা গাছ মিলে যায়:
গাছ ১ গাছ ২ গাছ ৩ গাছ ৪
A A A A
/ / \ \
B B B B
/ \ / \
C C C C
চারটার প্রতিটাতেই —
Preorder (Root, Left, Right) = A , B , C ← চারটাতেই একই
Postorder (Left, Right, Root) = C , B , A ← চারটাতেই একই
কিন্তু Inorder চারটার জন্য চার রকম:
| গাছ | B কোথায় | C কোথায় | Inorder |
|---|
| ১ | A এর বামে | B এর বামে | C B A |
| ২ | A এর বামে | B এর ডানে | B C A |
| ৩ | A এর ডানে | B এর বামে | A C B |
| ৪ | A এর ডানে | B এর ডানে | A B C |
না, unique হয় না।
কারণ: Preorder ও Postorder শুধু বলে কে root — বলে না কোন child বামে আর কোনটা ডানে।
একটামাত্র child থাকলে সেটা বাম না ডান, তা ঠিক করতে Inorder লাগবেই।
ব্যতিক্রম (বোনাস লাইন): যদি গাছটা full binary tree হয় (প্রতিটা node এর 0 বা 2টা
child), তখন "একটামাত্র child" এর সমস্যাটাই থাকে না — তখন Preorder + Postorder দিয়েও
unique tree বানানো যায়। খাতায় এই লাইনটা লিখলে বাড়তি নম্বর।
১০. Common Mistakes
- Postorder এ প্রথম element কে root ধরা — postorder এ root সবার শেষে। Preorder এর সাথে গুলিয়ে ফেলা সবচেয়ে সাধারণ ভুল।
- Element গুনতে ভুল করা — inorder এ বামে যতগুলো, preorder/postorder এ ঠিক ততগুলোই নিতে হবে। প্রতি ধাপে গুনে লিখে রাখো।
- একদিকে child না থাকলেও জোর করে বসিয়ে দেওয়া — inorder এ root এর এক পাশ খালি থাকলে সেই পাশ সত্যিই খালি।
- বাম-ডান উল্টে বসানো — inorder এ root এর যে পাশে আছে, গাছেও ঠিক সেই পাশে বসবে।
- শুধু উত্তর লেখা, ভাঙার ধাপ না দেখানো — split টেবিলটাই মূল নম্বরের জায়গা।
- শেষে যাচাই না করা — আঁকা গাছ থেকে inorder বের করে মিলিয়ে দেখা বাধ্যতামূলক ভাবো।
- Pre + Post দিয়ে গাছ এঁকে ফেলা — প্রশ্নটা ফাঁদ; উত্তর হলো "unique নয়" + উদাহরণ।
১১. Viva Questions
Q: Binary tree unique ভাবে তৈরি করতে কোন দুইটা traversal লাগে এবং কেন?
Q: Inorder ছাড়া গাছ বানানো যায় না কেন?
Q: Preorder + Postorder দিয়ে কখন unique tree পাওয়া যায়?
Q: Level order + Inorder দিয়ে কি গাছ বানানো যায়? কীভাবে?
Q: এই construction এর time complexity কত এবং কীভাবে O(n) করা যায়?
Q: Recursion এর base case এখানে কী?
Q: Inorder এ duplicate value থাকলে কী সমস্যা হবে?
১২. Practice Questions
Preorder = 1 2 4 5 3 6 7, Inorder = 4 2 5 1 6 3 7 — গাছ আঁকো ও Postorder লেখো।
উত্তর দেখাও
Root 1; বাম {4,2,5}, ডান {6,3,7}। বামের root 2 (বামে 4, ডানে 5)। ডানের root 3 (বামে 6, ডানে 7)।
এটা একটা perfect binary tree। Postorder = 4, 5, 2, 6, 7, 3, 1
Postorder = 8 4 5 2 6 7 3 1, Inorder = 8 4 2 5 1 6 3 7 — গাছ আঁকো ও Preorder লেখো।
উত্তর দেখাও
Root 1 (শেষ); বাম inorder {8,4,2,5} (৪টা), ডান {6,3,7} (৩টা)।
বামের postorder 8 4 5 2 → root 2; inorder 8 4 | 2 | 5 → বাম {8,4}, ডান {5}।
{8,4}: postorder 8 4 → root 4; inorder 8 4 → 8 হলো 4 এর left child।
ডানের postorder 6 7 3 → root 3; inorder 6 | 3 | 7 → বাম 6, ডান 7।
Preorder = 1, 2, 4, 8, 5, 3, 6, 7
Preorder = P Q R, Postorder = R Q P — unique গাছ হয় কি? সব সম্ভাব্য গাছ আঁকো।
উত্তর দেখাও
না। ৪টা গাছ সম্ভব — Q কে P এর বামে বা ডানে, আর R কে Q এর বামে বা ডানে বসিয়ে।
Inorder ছাড়া কোনটা সঠিক তা বলা যায় না।
Inorder = D B E A F C মাত্র এইটুকু দেওয়া থাকলে কয়টা আলাদা গাছ সম্ভব? ব্যাখ্যা করো।- একটা গাছের Preorder ও Inorder একই হলে গাছটার গঠন কেমন?
উত্তর দেখাও
প্রতিটা node এর শুধু right child থাকবে — অর্থাৎ ডান দিকে হেলে পড়া (right-skewed) গাছ, যেটা আসলে একটা linked list।
- একটা গাছের Inorder ও Postorder একই হলে গঠন কেমন?
উত্তর দেখাও
প্রতিটা node এর শুধু left child থাকবে — বাম দিকে হেলে পড়া (left-skewed) গাছ।
Preorder = A B C D E F, Inorder = C B D A E F — গাছ আঁকো, height বের করো এবং Postorder লেখো।
উত্তর দেখাও
Root A; বাম {C,B,D}, ডান {E,F}। বামের root B (বামে C, ডানে D)। ডানের preorder E F, inorder E F → root E, F হলো E এর right child।
Height = 2 (edge গুনে)। Postorder = C, D, B, F, E, A
- Construction এর pseudocode লেখো এবং কেন hash map ব্যবহার করলে O(n) হয় তা ব্যাখ্যা করো।