Topic 07 · Binary Search Tree
BST — Creation ও Insertion
একটা সংখ্যার তালিকা দিয়ে BST বানানো — পরীক্ষায় প্রায় নিশ্চিত প্রশ্ন। নিয়ম মাত্র একটাই:
ছোট হলে বামে, বড় হলে ডানে — root থেকে শুরু করে খালি জায়গা পাওয়া পর্যন্ত।
Exam Chance ≈ 95%
★★★
সময় ≈ ১০ মিনিট
পরের ধাপ: Deletion
১. প্রশ্ন (Question)
EXAM QUESTION
নিচের সংখ্যাগুলো ক্রমানুসারে insert করে একটা Binary Search Tree তৈরি করো এবং
প্রতিটি ধাপ দেখাও:
45, 25, 65, 15, 30, 55, 75, 20, 35
তৈরি হওয়া গাছটির Inorder, Preorder, Postorder traversal লেখো এবং
height বের করো।
২. Prerequisite Concepts (আগে যা জানা দরকার)
২.১ BST কী?
Binary Search Tree হলো এমন একটা binary tree যেখানে প্রতিটা node এর জন্য —
• বাম subtree এর সব value ওই node এর চেয়ে ছোট
• ডান subtree এর সব value ওই node এর চেয়ে বড়
কেন দরকার: এই একটামাত্র শর্তের কারণেই খোঁজার সময় প্রতিবার অর্ধেক গাছ বাদ দেওয়া যায় —
তাই search O(log n)। শর্তটা মনে না থাকলে গাছই ভুল হবে।
খুব সূক্ষ্ম কিন্তু জরুরি কথা: শর্তটা শুধু
সরাসরি child এর জন্য নয়,
পুরো subtree এর
জন্য। নিচের গাছটা দেখো:
10
/ \
5 15
/ \
8 20 ← 8 আছে 15 এর বামে, শর্ত ঠিক মনে হচ্ছে…
কিন্তু 8 আছে root 10 এর
ডান subtree তে, অথচ 8 < 10। তাই এটা BST
নয়।
২.২ Duplicate value নিয়ে কী হবে?
সাধারণ BST তে duplicate রাখা হয় না। প্রশ্নে duplicate থাকলে খাতায় লিখে দাও —
"duplicate ignore করা হলো" অথবা "duplicate কে ডানে রাখা হলো" — এবং পুরো সমাধানে
একই নিয়ম মেনে চলো।
কেন দরকার: নিয়ম না লিখে দিলে examiner ধরে নেবে তুমি ভুল করেছ।
২.৩ Inorder traversal — BST এর সবচেয়ে বড় বৈশিষ্ট্য
যেকোনো BST এর Inorder traversal সবসময় sorted (ছোট থেকে বড়) ক্রমে আসে।
কেন হয়: Inorder এর ক্রম হলো Left → Root → Right, আর BST তে বামের সব ছোট, ডানের সব বড়।
তাই স্বাভাবিকভাবেই ছোট থেকে বড় ক্রমে বের হয়।
কেন দরকার: এটাই তোমার বিনামূল্যে যাচাই — গাছ আঁকার পর inorder বের করে দেখো
sorted কিনা। না হলে কোথাও ভুল আছে।
২.৪ Height ও Level
Height = root থেকে সবচেয়ে দূরের leaf পর্যন্ত edge সংখ্যা।
(কিছু বই node গুনে, তখন height = edge + 1। খাতায় কোন সংজ্ঞা ব্যবহার করছ লিখে দাও।)
Level = root এর level 0, তার child দের level 1, এভাবে।
কেন দরকার: BST এর search time নির্ভর করে height এর উপর — height যত কম, search তত দ্রুত।
২.৫ Insert করার ক্রম গাছের আকার বদলে দেয়
একই সংখ্যাগুলো ভিন্ন ক্রমে insert করলে ভিন্ন গাছ তৈরি হয়।
যেমন 10, 20, 30, 40 ক্রমে insert করলে গাছটা একটা সরলরেখা হয়ে যায়
(skewed tree), তখন search O(n) — linked list এর মতোই খারাপ।
কেন দরকার: "BST এর worst case কী?" — এই viva প্রশ্নের উত্তর এখানেই।
৩. Exam Definition (English)
Binary Search Tree: A binary search tree is a binary tree in which, for every node
x, all keys stored in the left subtree of x are less than
x.key, and all keys stored in the right subtree of x are greater than
x.key.
Insertion: To insert a key, the search starts at the root and compares the key with the
current node. If the key is smaller, the search moves to the left child; if it is larger, it moves
to the right child. This continues until an empty position (NULL link) is reached, where the new
node is attached as a leaf. Insertion never restructures the existing tree.
Complexity: O(h), where h is the height of the tree —
O(log n) for a balanced tree and O(n) in the worst case of a skewed tree.
৪. Concept Explanation (বাংলায়)
ভাবো তুমি একটা অভিধানে শব্দ খুঁজছ। মাঝখান থেকে খুলে দেখলে — খোঁজা শব্দটা যদি আগে আসে,
তাহলে বাকি অর্ধেক আর দেখারই দরকার নেই। BST ঠিক এই কাজটাই করে।
নতুন একটা সংখ্যা বসাতে হলে root থেকে শুরু করো। প্রতিটা node এ দাঁড়িয়ে একটাই প্রশ্ন:
"আমি কি এই সংখ্যার চেয়ে ছোট, না বড়?" ছোট হলে বামে নামো, বড় হলে ডানে। এভাবে নামতে
নামতে একসময় এমন জায়গায় পৌঁছাবে যেখানে আর কোনো child নেই — সেই খালি জায়গাতেই
নতুন node বসবে।
সবচেয়ে গুরুত্বপূর্ণ কথা: নতুন node সবসময় leaf হিসেবেই যোগ হয়। আগের কোনো node
এর জায়গা বদলায় না, কেউ উপরে-নিচে সরে না। Heap এর insertion এর সাথে এখানেই বড় পার্থক্য —
সেখানে bubble up করে জায়গা বদলাতে হয়, এখানে নয়।
৫. Algorithm (English)
BST_INSERT(root, key)
if root == NULL then
return new Node(key) // empty spot found — place it here
if key < root.key then
root.left = BST_INSERT(root.left, key)
else if key > root.key then
root.right = BST_INSERT(root.right, key)
// else: key already exists — ignore (no duplicates)
return root
BST_CREATE(list of keys)
root = NULL
for each key in the list, in the given order do
root = BST_INSERT(root, key)
return root
Iterative রূপ (একই কাজ, loop দিয়ে): current = root ধরো; key < current হলে
current = current.left, বড় হলে current = current.right; যেখানে current NULL হয়ে যায়,
তার parent এর ওই পাশে নতুন node জুড়ে দাও।
৬. ধাপে ধাপে ব্যাখ্যা (বাংলায়)
ধাপ ১ — প্রথম সংখ্যাটাই root
তালিকার প্রথম সংখ্যা 45 — গাছ খালি ছিল, তাই 45 root হয়ে বসল।
কেন: খালি গাছে তুলনা করার মতো কিছু নেই, তাই প্রথমটা সরাসরি root।
এজন্যই insert এর ক্রম বদলালে গাছও বদলে যায়।
ধাপ ২ — প্রতিটা নতুন সংখ্যার জন্য root থেকে শুরু করো
কখনোই মাঝখান থেকে শুরু করবে না — প্রতিবার নতুন করে root থেকে নামতে হবে।
কেন: সঠিক জায়গা খুঁজতে হলে উপরের প্রতিটা তুলনা করা লাগবে,
নইলে BST এর শর্ত ভেঙে যাবে।
ধাপ ৩ — তুলনা করে দিক ঠিক করো
নতুন < বর্তমান → বামে নামো।
নতুন > বর্তমান → ডানে নামো।
কেন: এটাই BST এর মূল শর্ত। প্রতিটা তুলনায় গাছের একটা অর্ধেক বাদ পড়ে যায় —
এজন্যই search দ্রুত।
ধাপ ৪ — খালি জায়গা পেলে সেখানেই বসাও
যে দিকে নামতে চাচ্ছ সেদিকে কোনো child না থাকলে (NULL), সেখানেই নতুন node বসবে।
কেন leaf হিসেবেই: কারণ পথের প্রতিটা তুলনা ইতিমধ্যেই মেনে চলা হয়েছে,
তাই ওই খালি জায়গাটাই একমাত্র বৈধ জায়গা।
ধাপ ৫ — শেষে Inorder দিয়ে যাচাই করো
সব insert শেষ হলে inorder traversal বের করো — sorted হলে গাছ নিশ্চিতভাবে ঠিক আছে।
কেন দরকার: এক লাইনে পুরো গাছ যাচাই হয়ে যায়। খাতায় এই লাইনটা লিখলে
examiner বোঝে তুমি property টা বুঝেছ।
৭. প্রতিটা Insert এর ছবি
Insert 45 — গাছ খালি, তাই root
45
Insert 25 — 25 < 45 → বামে
45
/
25
Insert 65 — 65 > 45 → ডানে
45
/ \
25 65
Insert 15 — 15 < 45 → বাম (25); 15 < 25 → বাম, খালি ✓
45
/ \
25 65
/
15
Insert 30 — 30 < 45 → বাম (25); 30 > 25 → ডান, খালি ✓
45
/ \
25 65
/ \
15 30
Insert 55 — 55 > 45 → ডান (65); 55 < 65 → বাম, খালি ✓
45
/ \
25 65
/ \ /
15 30 55
Insert 75 — 75 > 45 → ডান (65); 75 > 65 → ডান, খালি ✓
45
/ \
25 65
/ \ / \
15 30 55 75
Insert 20 — 20 < 45 → 25; 20 < 25 → 15; 20 > 15 → ডান, খালি ✓
45
/ \
25 65
/ \ / \
15 30 55 75
\
20
Insert 35 — 35 < 45 → 25; 35 > 25 → 30; 35 > 30 → ডান, খালি ✓
45
/ \
25 65
/ \ / \
15 30 55 75
\ \
20 35
চূড়ান্ত BST · 9 টা node · height = 3
৮. সমাধান — সম্পূর্ণ ট্রেস
খেয়াল করো: 20 বসেছে 15 এর ডানে, যদিও 20 < 25। এটা ভুল মনে হতে পারে,
কিন্তু ঠিক আছে — কারণ 20 কে 15 এর সাথেও তুলনা করতে হয়েছে, আর 20 > 15। শর্ত দুইটাই মানা
হয়েছে: 20 আছে 25 এর বাম subtree তে (20 < 25 ✓) এবং 15 এর ডানে (20 > 15 ✓)।
Traversal গুলো
Inorder (Left, Root, Right) : 15 , 20 , 25 , 30 , 35 , 45 , 55 , 65 , 75
Preorder (Root, Left, Right) : 45 , 25 , 15 , 20 , 30 , 35 , 65 , 55 , 75
Postorder (Left, Right, Root) : 20 , 15 , 35 , 30 , 25 , 55 , 75 , 65 , 45
যাচাই: Inorder পুরোপুরি sorted (ছোট → বড়) ✓ — অর্থাৎ গাছটা বৈধ BST।
Height ও Level
| Level | Node গুলো | কয়টা |
|---|
| 0 | 45 | 1 |
| 1 | 25, 65 | 2 |
| 2 | 15, 30, 55, 75 | 4 |
| 3 | 20, 35 | 2 |
Height = 3 (edge গুনে; সবচেয়ে লম্বা পথ 45 → 25 → 15 → 20, মোট ৩টা edge)।
Node গুনলে height = 4।
৯. Final Exam Answer (English)
Final BST after inserting 45, 25, 65, 15, 30, 55, 75, 20, 35
45
/ \
25 65
/ \ / \
15 30 55 75
\ \
20 35
Inorder : 15, 20, 25, 30, 35, 45, 55, 65, 75 (sorted ✓)
Preorder : 45, 25, 15, 20, 30, 35, 65, 55, 75
Postorder: 20, 15, 35, 30, 25, 55, 75, 65, 45
Height = 3 (edges) · Nodes = 9 · Insertion cost O(h)
১০. Common Mistakes
- Root থেকে না নেমে চোখের আন্দাজে বসিয়ে দেওয়া — প্রতিটা সংখ্যার জন্য root থেকে পুরো পথ হাঁটতে হবে।
- শুধু সরাসরি parent এর সাথে তুলনা করা — পথের প্রতিটা node এর সাথেই তুলনা হয়। subtree এর সব value কে মানতে হয়।
- নতুন node কে মাঝখানে ঢুকিয়ে দেওয়া — BST তে নতুন node সবসময় leaf। কোনো node সরানো হয় না।
- Insert এর ক্রম বদলে ফেলা — প্রশ্নে যে ক্রমে দেওয়া, ঠিক সেই ক্রমেই বসাতে হবে; ক্রম বদলালে গাছও বদলায়।
- Inorder দিয়ে যাচাই না করা — sorted না এলে গাছ ভুল, এটা ধরার সহজতম উপায়।
- Height এ node আর edge গুলিয়ে ফেলা — কোন সংজ্ঞা ব্যবহার করছ খাতায় লিখে দাও।
- ধাপগুলো না দেখিয়ে শুধু শেষ গাছ আঁকা — "প্রতিটা ধাপ দেখাও" বললে প্রতিটা ধাপের গাছ বা tracing table লাগবে; নম্বর ওখানেই।
১১. Viva Questions
Q: BST এর সংজ্ঞা দাও। Binary Tree আর BST এর পার্থক্য কী?
Q: BST এর Inorder traversal সবসময় sorted হয় কেন?
Q: Insertion এর time complexity কত? Worst case কখন হয় এবং কেন?
Q: একই সংখ্যাগুলো ভিন্ন ক্রমে insert করলে কি একই গাছ পাওয়া যায়? উদাহরণ দাও।
Q: Skewed BST কী? সেটা এড়াতে কী ব্যবহার করা হয়? (উত্তর: AVL / Red-Black tree)
Q: BST তে নতুন node কি কখনো internal node হিসেবে যোগ হতে পারে? কেন নয়?
Q: BST তে সবচেয়ে ছোট আর সবচেয়ে বড় value কোথায় থাকে? (উত্তর: সবচেয়ে বামের ও সবচেয়ে ডানের node)
Q: n টা node এর BST এর সর্বনিম্ন ও সর্বোচ্চ height কত?
১২. Practice Questions
50, 30, 70, 20, 40, 60, 80 — BST বানাও এবং তিনটা traversal লেখো।
উত্তর দেখাও
একদম নিখুঁত সুষম (perfect) গাছ: root 50; বামে 30 (child 20, 40); ডানে 70 (child 60, 80)।
Inorder = 20, 30, 40, 50, 60, 70, 80 ✓ · Preorder = 50, 30, 20, 40, 70, 60, 80 ·
Postorder = 20, 40, 30, 60, 80, 70, 50 · Height = 2
10, 20, 30, 40, 50 — BST বানাও। গাছটার আকার কেমন হলো এবং search এর complexity কত?
উত্তর দেখাও
প্রতিটাই আগেরটার চেয়ে বড়, তাই সব ডানে বসবে — right-skewed গাছ, দেখতে linked list এর মতো।
Height = 4, search = O(n)। এটাই BST এর worst case।
- একই সংখ্যাগুলো
50, 40, 30, 20, 10 ক্রমে insert করলে গাছ কেমন হবে?
উত্তর দেখাও
সব বামে বসবে — left-skewed গাছ। Height = 4, search = O(n)।
60, 25, 80, 15, 45, 70, 90, 35, 55 — BST বানাও, height বের করো এবং 55 খুঁজতে কয়টা তুলনা লাগবে দেখাও।
উত্তর দেখাও
Root 60; বামে 25 (child 15, 45; 45 এর child 35 ও 55); ডানে 80 (child 70, 90)।
Height = 3। 55 খুঁজতে: 55 < 60 → 25 · 55 > 25 → 45 · 55 > 45 → 55 পাওয়া গেল = 3 টা তুলনা।
- 7 টা node দিয়ে সবচেয়ে কম height এর BST এর height কত? সেটা বানাতে কোন ক্রমে insert করবে?
উত্তর দেখাও
সর্বনিম্ন height = 2 (কারণ 2³ − 1 = 7)। sorted তালিকার মাঝখানের element আগে নিতে হবে —
যেমন 40, 20, 60, 10, 30, 50, 70।
- নিচের গাছটা কি বৈধ BST? কারণ ব্যাখ্যা করো:
20
/ \
10 30
/ \
25 15
উত্তর দেখাও
না। 15 আছে root 20 এর ডান subtree তে, কিন্তু 15 < 20 — শর্ত ভাঙছে।
(সহজ যাচাই: inorder = 10, 20, 25, 30, 15 — sorted নয়।)
- একটা BST তে minimum আর maximum value খোঁজার algorithm লেখো এবং complexity বলো।
M, A, R, K, S — অক্ষরগুলো alphabetical তুলনা ধরে BST বানাও।
উত্তর দেখাও
Root M; A < M → বামে; R > M → ডানে; K > A → A এর ডানে; S > M → R এর ডানে।
Inorder = A, K, M, R, S ✓ (বর্ণক্রমে sorted)