কনসেপ্ট
একটি দেওয়া ব্যালেন্সড বাইনারি সার্চ ট্রি (Balanced Binary Search Tree) এবং একটি টার্গেট সম (target sum) বিবেচনা করে, আমরা একটি ফাংশন লিখব যা true রিটার্ন করবে যদি সমের সাথে সমান একটি জোড়া (pair) থাকে, অন্যথায় false রিটার্ন করবে। এই কেসে এক্সপেক্টেড টাইম কমপ্লেক্সিটি O(n) এবং শুধু O(log n) এক্সট্রা স্পেস বাস্তবায়ন করা যাবে। এখানে বাইনারি সার্চ ট্রিতে কোনো মডিফিকেশন অনুমোদিত নয়। মনে রাখবেন ব্যালেন্সড BST-এর হাইট সবসময় O(log n)।
উদাহরণ
মেথড
Brute Force সমাধান অনুযায়ী, আমরা BST-এ প্রতিটি জোড়া বিবেচনা করি এবং যাচাই করি যোগফল X-এর সমান কিনা। এই সমাধানের টাইম কমপ্লেক্সিটি হবে O(n²)।
একটি ভালো সমাধান হলো একটি অক্সিলিয়ারি অ্যারে তৈরি করা এবং BST-এর ইনঅর্ডার ট্রভারসাল (inorder traversal) অ্যারেতে স্টোর করা। এই কেসে, অ্যারেটি সর্টেড হবে কারণ BST-এর ইনঅর্ডার ট্রভারসাল সবসময় সর্টেড ডেটা প্রডিউস করে। ইনঅর্ডার ট্রভারসাল পাওয়ার পর, আমরা O(n) টাইমে জোড়া খুঁজে বের করতে পারি। মনে রাখবেন, এই সমাধান O(n) টাইমে কাজ করে, কিন্তু O(n) অক্সিলিয়ারি স্পেস দরকার।
উদাহরণ
// Java code to find a pair with given sum
// in a Balanced BST
import java.util.ArrayList;
// A binary tree node
class Node1 {
int data1;
Node1 left1, right1;
Node1(int d){
data1 = d;
left1 = right1 = null;
}
}
public class BinarySearchTree {
// BST-এর রুট নির্দেশ করে
Node1 root1;
// কনস্ট্রাক্টর
BinarySearchTree(){
root1 = null;
}
// ট্রি-এর ইনঅর্ডার ট্রভারসাল
void inorder(){
inorderUtil1(this.root1);
}
// ইনঅর্ডার ট্রভারসালের ইউটিলিটি ফাংশন
void inorderUtil1(Node1 node1){
if (node1 == null)
return;
inorderUtil1(node1.left1);
System.out.print(node1.data1 + " ");
inorderUtil1(node1.right1);
}
// এই মেথড মূলত insertRec()-কে কল করে
void insert(int key1){
root1 = insertRec1(root1, key1);
}
/* BST-এ একটি নতুন কী ইনসার্ট করার রিকার্সিভ ফাংশন */
Node1 insertRec1(Node1 root1, int data1){
if (root1 == null) {
root1 = new Node1(data1);
return root1;
}
if (data1 < root1.data1)
root1.left1 = insertRec1(root1.left1, data1);
else if (data1 > root1.data1)
root1.right1 = insertRec1(root1.right1, data1);
return root1;
}
// BST-এর মানগুলো ArrayList-এ যোগ করে রিটার্ন করে
ArrayList treeToList(Node1 node1, ArrayList list1){
if (node1 == null)
return list1;
treeToList(node1.left1, list1);
list1.add(node1.data1);
treeToList(node1.right1, list1);
return list1;
}
// জোড়া আছে কিনা চেক করে
boolean isPairPresent(Node1 node1, int target1){
ArrayList a1 = new ArrayList<>();
ArrayList a2 = treeToList(node1, a1);
int start1 = 0;
int end1 = a2.size() - 1;
while (start1 < end1) {
if (a2.get(start1) + a2.get(end1) == target1) {
System.out.println("Pair Found: " + a2.get(start1) + " + " + a2.get(end1) + " = " + target1);
return true;
}
if (a2.get(start1) + a2.get(end1) > target1)
end1--;
if (a2.get(start1) + a2.get(end1) < target1)
start1++;
}
System.out.println("No such values are found!");
return false;
}
// ড্রাইভার ফাংশন
public static void main(String[] args){
BinarySearchTree tree1 = new BinarySearchTree();
/*
16
/ \
11 21
/ \ / \
9 13 17 26
*/
tree1.insert(16);
tree1.insert(11);
tree1.insert(21);
tree1.insert(9);
tree1.insert(13);
tree1.insert(17);
tree1.insert(26);
tree1.isPairPresent(tree1.root1, 34);
}
}
আউটপুট
Pair Found: 13 + 21 = 34
