Topic 09 · Binary Search Tree
Traversal থেকে BST তৈরি
সাধারণ binary tree তে দুইটা traversal লাগত। কিন্তু BST তে একটাই যথেষ্ট —
কারণ BST এর Inorder এমনিতেই sorted, সেটা আমরা নিজেরাই বানিয়ে নিতে পারি।
Exam Chance ≈ 70%
★★
সময় ≈ ১২ মিনিট
সবচেয়ে সহজ শর্টকাট আছে
১. প্রশ্ন (Question)
EXAM QUESTION
(a) Preorder = 45, 25, 15, 20, 30, 35, 65, 55, 75 — BST টি তৈরি করো
এবং Inorder ও Postorder লেখো।
(b) Postorder = 20, 15, 35, 30, 25, 55, 75, 65, 45 — BST টি তৈরি করো।
(c) শুধু Inorder দেওয়া থাকলে কি unique BST বানানো যায়? ব্যাখ্যা করো।
২. Prerequisite Concepts (আগে যা জানা দরকার)
২.১ BST এর গোপন সুবিধা
সাধারণ binary tree তে গাছ বানাতে
দুইটা traversal লাগে (
Topic 06 দেখো)।
কিন্তু BST তে
একটাই যথেষ্ট।
কেন: কারণ BST এর Inorder সবসময়
sorted। তাই Preorder দেওয়া থাকলে সেটাকে
sort করলেই Inorder পেয়ে যাই — অর্থাৎ দ্বিতীয় traversal টা
নিজেরাই বানিয়ে নিতে পারি।
এই এক লাইনেই পুরো টপিকটা দাঁড়ানো।
২.২ Preorder / Postorder এ root কোথায়
| Traversal | Root কোথায় | কীভাবে ভাগ করব |
|---|
| Preorder | সবার প্রথমে | প্রথম যে element root এর চেয়ে বড়, তার আগ পর্যন্ত বাম |
| Postorder | সবার শেষে | root এর চেয়ে ছোটগুলো বাম, বড়গুলো ডান |
কেন দরকার: এখানে সাধারণ binary tree এর মতো "গুনে গুনে" ভাগ করতে হয় না —
মান তুলনা করেই ভাগ করা যায়। এটাই BST কে সহজ করে দেয়।
২.৩ Preorder এ ছোট-বড় দল বাঁধে
Preorder এ root এর পরে প্রথমে পুরো বাম subtree আসে (সবাই root এর চেয়ে ছোট),
তারপর পুরো ডান subtree (সবাই বড়)। তাই তালিকায় যেখানে প্রথমবার root এর চেয়ে
বড় একটা সংখ্যা পাওয়া যায়, ঠিক সেখান থেকেই ডান subtree শুরু।
কেন দরকার: এই "প্রথম বড় সংখ্যাটা খোঁজো" নিয়মটাই কাঁচি — এক কোপে দুই ভাগ।
২.৪ কোন কোন তথ্য থেকে unique BST হয়
| যা দেওয়া আছে | Unique BST? | কেন |
|---|
| Preorder একা | হ্যাঁ ✓ | sort করলেই inorder পাওয়া যায় |
| Postorder একা | হ্যাঁ ✓ | একই কারণ |
| Level order একা | হ্যাঁ ✓ | একে একে insert করলেই হয় |
| Inorder একা | না ✗ | সব BST এরই inorder একই sorted list |
মনে রাখার কথা: "Inorder ছাড়া সব একা একাই চলে; Inorder একা কিছুই বলে না।"
৩. Exam Definition (English)
BST Construction from a Single Traversal: Because the inorder traversal of a binary
search tree is always the sorted sequence of its keys, a BST can be reconstructed uniquely from
its preorder traversal alone, or from its postorder traversal alone. The first element of the
preorder (or the last element of the postorder) is the root; the remaining elements are split by
comparison with the root — all keys smaller than the root form the left subtree and all keys
larger form the right subtree. The procedure is applied recursively to each part.
Note: The inorder traversal alone does not determine a BST uniquely, since every
BST built from the same set of keys produces exactly the same sorted inorder sequence. The number
of distinct BSTs on n distinct keys is the Catalan number
C(n) = (2n)! / (n! (n+1)!).
৪. Concept Explanation (বাংলায়)
Preorder মানে আমরা root কে সবার আগে দেখেছি, তারপর বামের সবাইকে, শেষে ডানের সবাইকে।
BST বলে আমরা জানি — বামের সবাই root এর চেয়ে ছোট, ডানের সবাই বড়।
তাহলে তালিকাটা এভাবে দেখো:
45 | 25 15 20 30 35 | 65 55 75
↑ └── সবাই 45 এর ──┘ └─ সবাই 45 এর ─┘
root চেয়ে ছোট চেয়ে বড়
তালিকায় হাঁটতে হাঁটতে যেই
প্রথম এমন সংখ্যা পেলে যেটা root এর চেয়ে বড় (এখানে 65),
বুঝে নাও ওখানেই বাম শেষ, ডান শুরু। ব্যস, ভাগ হয়ে গেল।
এবার বামের অংশটা নিজেই একটা ছোট BST এর preorder, ডানের অংশটাও তাই। একই কাজ আবার —
এটাই recursion। প্রতিবার তালিকা ছোট হতে হতে একটা মাত্র সংখ্যায় পৌঁছালে সেটা leaf।
৫. তিনটা পদ্ধতি — কোনটা কখন
পদ্ধতি ১ — একে একে Insert করা (সবচেয়ে সহজ, পরীক্ষার জন্য সেরা)
Preorder এর সংখ্যাগুলো
যে ক্রমে আছে ঠিক সেই ক্রমে একটা খালি BST তে insert করে যাও।
কেন কাজ করে: Preorder এ parent সবসময় তার child দের আগে আসে।
তাই insert করতে গেলে parent আগেই বসে থাকে, আর child ঠিক তার নিচেই বসে —
হুবহু আসল গাছটাই তৈরি হয়।
Postorder এর ক্ষেত্রে: তালিকাটা উল্টে (reverse) নিয়ে একই কাজ করো।
কারণ postorder উল্টালে root আগে চলে আসে।
পদ্ধতি ২ — ভাগ করে ফেলা (Divide method — খাতায় দেখানোর জন্য সেরা)
Root নাও → বাকি তালিকাকে "ছোট" আর "বড়" দুই ভাগে ভাগ করো → প্রতিটা ভাগে একই কাজ করো।
কেন এটা দেখাবে: examiner ধাপ দেখতে চায়। এই পদ্ধতিতে একটা সুন্দর
ভাগ-করা টেবিল বানানো যায়, যেখানে প্রতিটা ধাপ পরিষ্কার — নম্বর এখানেই।
পদ্ধতি ৩ — Sort করে Inorder বানিয়ে নেওয়া (যাচাইয়ের জন্য)
Preorder কে sort করলেই Inorder। তারপর
Topic 06 এর
Pre + In পদ্ধতি প্রয়োগ করো।
কেন দরকার: এটা প্রমাণ করে দেয় কেন BST তে একটামাত্র traversal যথেষ্ট।
লিখিত ব্যাখ্যায় এই যুক্তিটা লিখলে বাড়তি নম্বর।
৬. ধাপে ধাপে ব্যাখ্যা (Divide পদ্ধতি)
ধাপ ১ — Root বের করো
Preorder হলে প্রথম সংখ্যা, Postorder হলে শেষ সংখ্যা।
কেন: সংজ্ঞা অনুযায়ীই preorder এ root আগে, postorder এ পরে ছাপা হয়।
ধাপ ২ — বাকিদের মান তুলনা করে দুই ভাগে ভাগ করো
Root এর চেয়ে ছোট সবাই → বাম subtree। বড় সবাই → ডান subtree।
কেন গুনতে হয় না: সাধারণ binary tree তে inorder দেখে গুনতে হতো।
BST তে মান নিজেই বলে দেয় কে কোন দিকে — এটাই BST এর সুবিধা।
ধাপ ৩ — ক্রম নষ্ট করো না
ভাগ করার সময় সংখ্যাগুলো তালিকায় যে ক্রমে ছিল, সেই ক্রমেই রাখো।
কেন জরুরি: প্রতিটা ভাগ নিজেই একটা বৈধ preorder/postorder।
ক্রম এলোমেলো করলে পরের ধাপে root ভুল বের হবে।
ধাপ ৪ — প্রতিটা ভাগে ধাপ ১–৩ আবার করো
একটা সংখ্যা বাকি থাকলে সেটাই leaf; কোনো সংখ্যা না থাকলে ওই দিক খালি।
কেন: প্রতিটা subtree নিজেও একটা সম্পূর্ণ BST — একই নিয়ম খাটে।
ধাপ ৫ — Inorder বের করে যাচাই করো
আঁকা গাছ থেকে inorder নাও — sorted হলে গাছ ঠিক আছে।
কেন নিশ্চিত হওয়া যায়: শুধু sorted হলেই হবে না, sorted তালিকাটা
দেওয়া সংখ্যাগুলোর সাথেও মিলতে হবে। দুইটা মিললে ভুল থাকার সুযোগ নেই।
৭. Q1 সমাধান — Preorder থেকে BST
Preorder = 45 , 25 , 15 , 20 , 30 , 35 , 65 , 55 , 75
Step 1 — Root = 45, তারপর ভাগ
45 | 25 15 20 30 35 | 65 55 75
↑ └──── < 45 ─────┘ └─── > 45 ───┘
root
প্রথম যে সংখ্যা 45 এর চেয়ে বড় → 65 ⇒ ওখান থেকেই ডান subtree শুরু
Step 2 — সম্পূর্ণ ভাগ-করা টেবিল
Step 3 — গাছ
45
/ \
25 65
/ \ / \
15 30 55 75
\ \
20 35
Step 4 — যাচাই ও উত্তর
Inorder : 15 , 20 , 25 , 30 , 35 , 45 , 55 , 65 , 75 ← sorted ✓
Postorder : 20 , 15 , 35 , 30 , 25 , 55 , 75 , 65 , 45
শর্টকাট দিয়ে ক্রস-চেক: preorder এর সংখ্যাগুলো ঠিক ওই ক্রমে একটা খালি BST তে
insert করো —
45, 25, 15, 20, 30, 35, 65, 55, 75। হুবহু একই গাছ পাবে।
(এটাই
Topic 07 এর প্রশ্নের গাছ।) খাতায় দুই পদ্ধতিতে
একই উত্তর দেখালে examiner নিশ্চিত হয় তুমি বুঝে করেছ।
BST তৈরি হলো ✓
Inorder : 15, 20, 25, 30, 35, 45, 55, 65, 75 (sorted ✓)
Postorder: 20, 15, 35, 30, 25, 55, 75, 65, 45
Height = 3 · Nodes = 9
৮. Q2 সমাধান — Postorder থেকে BST
Postorder = 20 , 15 , 35 , 30 , 25 , 55 , 75 , 65 , 45
↑
root
Step 1 — Root = 45 (শেষের সংখ্যা), তারপর ভাগ
20 15 35 30 25 | 55 75 65 | 45
└───── < 45 ──────┘ └── > 45 ──┘ ↑
root
খেয়াল করো: Postorder এ root শেষে থাকে, তাই ভাগ করার সময় বামের অংশ আগে,
ডানের অংশ পরে, root সবার শেষে। Preorder এর সাথে গুলিয়ে ফেলো না।
Step 2 — সম্পূর্ণ ভাগ-করা টেবিল
Step 3 — গাছ (Q1 এর সাথে হুবহু একই)
45
/ \
25 65
/ \ / \
15 30 55 75
\ \
20 35
শর্টকাট — Reverse Insert: Postorder কে উল্টে নাও —
45, 65, 75, 55, 25, 30, 35, 15, 20 — তারপর এই ক্রমে খালি BST তে insert করো।
একই গাছ পাবে।
কেন কাজ করে: Postorder উল্টালে root সবার আগে চলে আসে, আর প্রতিটা parent তার
child দের আগেই বসে যায় — ঠিক preorder insert এর মতোই।
একই BST পাওয়া গেল ✓
Preorder = 45, 25, 15, 20, 30, 35, 65, 55, 75 · Inorder = 15, 20, 25, 30, 35, 45, 55, 65, 75
৯. Q3 — শুধু Inorder দিয়ে কেন হয় না
ধরা যাক Inorder = 10, 20, 30। এটা যেকোনো BST এর inorder হতে পারে যেটা
এই তিনটা সংখ্যা দিয়ে বানানো — কারণ BST এর inorder সবসময়ই sorted। তাই আলাদা করে
কিছুই বোঝা যায় না।
গাছ ১ গাছ ২ গাছ ৩ গাছ ৪ গাছ ৫
10 10 20 30 30
\ \ / \ / /
20 30 10 30 10 20
\ / \ /
30 20 20 10
পাঁচটার প্রতিটার inorder একই: 10, 20, 30 — কিন্তু গাছ পাঁচ রকম।
কয়টা গাছ সম্ভব? n টা আলাদা সংখ্যা দিয়ে মোট
C(n) = (2n)! / (n! × (n+1)!) টা আলাদা BST বানানো যায় — একে
Catalan number বলে।
n = 3 → C(3) = 6! / (3! × 4!) = 720 / 144 = 5 ✓ (উপরের পাঁচটাই)
n = 4 → 14 টা · n = 5 → 42 টা
না, শুধু Inorder দিয়ে unique BST বানানো যায় না।
কারণ: একই সংখ্যাগুলোর সব BST এর inorder ই একই sorted list। n টা সংখ্যায়
Catalan(n) টা আলাদা BST সম্ভব।
Inorder এর সাথে Preorder বা Postorder এর একটা দিলেই unique হয়ে যায়।
১০. Common Mistakes
- Postorder এর প্রথম সংখ্যাকে root ধরা — postorder এ root সবার শেষে।
- ভাগ করার সময় ক্রম এলোমেলো করে ফেলা — "ছোট" গুলোকে আলাদা করে sort করে ফেললে পরের ধাপে root ভুল বের হবে। ক্রম যেমন ছিল তেমনই রাখো।
- সাধারণ binary tree এর মতো গুনে গুনে ভাগ করা — BST তে মান দেখে ভাগ হয়, গুনে নয়।
- Postorder কে উল্টে সরাসরি preorder ভাবা — reverse postorder আসল preorder নয়। তবে reverse করে insert করলে গাছ ঠিকই আসে — এই দুইটা আলাদা কথা।
- "Inorder একা যথেষ্ট" ভাবা — এটাই সবচেয়ে বড় ফাঁদ প্রশ্ন। উত্তর: না, উদাহরণসহ দেখাতে হবে।
- Insert শর্টকাট ব্যবহার করে কোনো ধাপ না দেখানো — শর্টকাটে উত্তর ঠিক আসে, কিন্তু নম্বর ধাপে। অন্তত ভাগ-করা টেবিলটা দাও।
- শেষে inorder মিলিয়ে না দেখা — sorted হচ্ছে কিনা এবং দেওয়া সংখ্যাগুলোই আছে কিনা, দুইটাই দেখো।
১১. Viva Questions
Q: BST তে একটা traversal দিয়েই গাছ বানানো যায়, কিন্তু সাধারণ binary tree তে দুইটা লাগে — কেন?
Q: Preorder থেকে BST বানানোর ধাপগুলো বলো।
Q: Inorder একা কেন যথেষ্ট নয়? উদাহরণ দাও।
Q: n টা সংখ্যা দিয়ে কয়টা আলাদা BST বানানো যায়? (উত্তর: Catalan number)
Q: Preorder এর সংখ্যাগুলো ক্রমে insert করলেই আসল গাছ পাওয়া যায় কেন?
Q: Postorder থেকে গাছ বানাতে reverse insert কেন কাজ করে?
Q: Level order traversal দিয়ে কি BST বানানো যায়?
Q: এই construction এর time complexity কত? Worst case কখন?
১২. Practice Questions
Preorder = 50, 30, 20, 40, 70, 60, 80 — BST বানাও এবং Postorder লেখো।
উত্তর দেখাও
Root 50; বাম 30 20 40 → root 30 (বামে 20, ডানে 40); ডান 70 60 80 → root 70 (বামে 60, ডানে 80)।
Postorder = 20, 40, 30, 60, 80, 70, 50 · Inorder = 20, 30, 40, 50, 60, 70, 80 ✓
Postorder = 20, 40, 30, 60, 80, 70, 50 — BST বানাও এবং Preorder লেখো।
উত্তর দেখাও
উপরের গাছটাই ফিরে আসবে। Preorder = 50, 30, 20, 40, 70, 60, 80
Preorder = 10, 20, 30, 40 — গাছটা কেমন হবে?
উত্তর দেখাও
প্রতিটা পরেরটা আগেরটার চেয়ে বড় → root 10 এর বাম subtree খালি, সব ডানে —
right-skewed গাছ (10 → 20 → 30 → 40)। Height = 3।
Preorder = 40, 30, 35, 32, 60, 50, 70 — BST বানাও এবং height বের করো।
উত্তর দেখাও
Root 40; বাম 30 35 32, ডান 60 50 70।
বাম: root 30 → বাম খালি, ডান 35 32 → root 35, বামে 32।
ডান: root 60 → বামে 50, ডানে 70।
Inorder = 30, 32, 35, 40, 50, 60, 70 ✓ · Height = 3 (40 → 30 → 35 → 32)
Inorder = 5, 10, 15, 20 — কয়টা আলাদা BST সম্ভব?
উত্তর দেখাও
n = 4 → C(4) = 8! / (4! × 5!) = 40320 / 2880 = 14 টা।
Level order = 45, 25, 65, 15, 30, 55, 75 — BST বানাও।
উত্তর দেখাও
এই ক্রমেই একে একে insert করে দাও — root 45; 25 বামে, 65 ডানে; 15 ও 30 হলো 25 এর দুই child;
55 ও 75 হলো 65 এর দুই child। একটা perfect BST।
- একই সংখ্যার সেট দিয়ে বানানো দুইটা আলাদা BST এর কোন traversal সবসময় একই থাকবে এবং কেন?
উত্তর দেখাও
Inorder — কারণ সেটা সবসময় sorted, আর সংখ্যার সেট একই।
- Preorder থেকে BST বানানোর pseudocode লেখো (range/bound পদ্ধতিতে) এবং complexity বলো।