সমস্যা বিবরণ
একটি বাইনারি ট্রি দেওয়া আছে। এটি বাইনারি সার্চ ট্রি (BST)-তে কনভার্ট করতে হবে এমনভাবে যে বাইনারি ট্রির মূল স্ট্রাকচার অক্ষুণ্ণ থাকে। এখানে অ্যারে-ভিত্তিক সমাধানের পরিবর্তে C++ STL-এর সেট (set) ব্যবহার করা হয়েছে।
উদাহরণ
উদাহরণ ১
ইনপুট
11 / \ 3 8 / \ 9 5
আউটপুট
9 / \ 5 11 / 3 8
উদাহরণ ২
ইনপুট
11 / \ 31 16 / \ 21 6
আউটপুট
16 / \ 11 21 / \ 6 31
সমাধান
- ইনঅর্ডার ট্রাভার্সাল দিয়ে বাইনারি ট্রির আইটেমগুলো সেটে কপি করুন। এতে O(n log n) সময় লাগে। C++ STL-এ set রেড-ব্ল্যাক ট্রি বা AVL ট্রি দিয়ে ইমপ্লিমেন্টেড, তাই ইনসার্ট, সার্চ, ডিলিট O(log n)।
- সেট সো্র্ট করার প্রয়োজন নেই, কারণ সেট ডিফল্টভাবে সো্র্টেড থাকে।
- ইনঅর্ডার ট্রাভার্সাল দিয়ে সেটের এলিমেন্টগুলো একে একে ট্রিতে কপি করুন। প্রতিটি কপি করার পর সেট থেকে সেই এলিমেন্ট ডিলিট করুন।
- এই পদ্ধতি অ্যারে-ভিত্তিক কনভার্সনের চেয়ে সহজ ও ইমপ্লিমেন্ট করা সহজ।
C++ কোড উদাহরণ
/* CPP program for converting a Binary tree to BST implementing sets as containers. */
#include <bits/stdc++.h>
using namespace std;
struct Node1 {
int data;
struct Node1 *left, *right;
};
// ইনঅর্ডার ট্রাভার্সাল দিয়ে নোডগুলো সেটে স্টোর করা
void storeinorderInSet(Node1* root1, set<int>& s) {
if (!root1) return;
storeinorderInSet(root1->left, s);
s.insert(root1->data); // O(log n)
storeinorderInSet(root1->right, s);
}
// সেট থেকে এলিমেন্ট কপি করে ট্রি আপডেট করা
void setToBST(set<int>& s, Node1* root1) {
if (!root1) return;
setToBST(s, root1->left);
auto it = s.begin();
root1->data = *it;
s.erase(it);
setToBST(s, root1->right);
}
// বাইনারি ট্রি থেকে BST কনভার্সন
void binaryTreeToBST(Node1* root1) {
set<int> s;
storeinorderInSet(root1, s);
setToBST(s, root1);
}
// হেল্পার ফাংশন
Node1* newNode(int data) {
Node1* temp = new Node1();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void inorder(Node1* root1) {
if (!root1) return;
inorder(root1->left);
cout << root1->data << " ";
inorder(root1->right);
}
int main() {
Node1* root1 = newNode(6);
root1->left = newNode(8);
root1->right = newNode(10);
root1->right->left = newNode(11);
root1->left->left = newNode(2);
root1->left->right = newNode(7);
root1->right->right = newNode(12);
binaryTreeToBST(root1);
cout << "Inorder traversal of BST is: " << endl;
inorder(root1);
return 0;
}
আউটপুট
Inorder traversal of BST is: 1 5 6 7 9 10 11
Time Complexity: O(n Log n)
Auxiliary Space: O(n)
