अवधारणा
एक दिए गए बैलेंस्ड बाइनरी सर्च ट्री और एक टारगेट योग के संबंध में, हम एक फ़ंक्शन लिखते हैं जो true वापस करता है यदि कोई जोड़ी है जिसका योग टारगेट योग के बराबर है, अन्यथा false वापस करता है। इस मामले में, अपेक्षित समय जटिलता O(n) है और केवल O(log n) अतिरिक्त स्पेस लागू किया जा सकता है। यहां, बाइनरी सर्च ट्री में कोई संशोधन अनुमत नहीं है। हमें ध्यान देना होगा कि बैलेंस्ड BST की ऊंचाई हमेशा O(log n) होती है।
उदाहरण

विधि
ब्रूट फोर्स समाधान के अनुसार, हम BST में प्रत्येक जोड़ी पर विचार करते हैं और सत्यापित करते हैं कि क्या योग X के बराबर है। इस समाधान की समय जटिलता O(n^2) होगी।
अब एक बेहतर समाधान एक सहायक ArrayList बनाना है और BST के इनऑर्डर ट्रैवर्सल को ArrayList में स्टोर करना है। इस मामले में, ArrayList क्रमबद्ध होगा क्योंकि 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 वापस करता है
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){
// अब यह list a1 एक आर्गुमेंट के रूप में पास की जाती है
// treeToList मेथड में
// जिसे बाद में BST के मानों से भरा जाता है
ArrayList a1 = new ArrayList<>();
// अब a2 लिस्ट में BST के सभी मान होते हैं
// treeToList मेथड द्वारा वापस किए गए
ArrayList a2 = treeToList(node1, a1);
int start1 = 0; // a2 का शुरुआती इंडेक्स इंगित करता है
int end1 = a2.size() - 1; // a2 का अंतिम इंडेक्स इंगित करता है
while (start1 < end1) {
if (a2.get(start1) + a2.get(end1) == target1) // टारगेट मिला!{
System.out.println("जोड़ी मिली: " + a2.get(start1) + " + " + a2.get(end1) + " = " + target1);
return true;
}
if (a2.get(start1) + a2.get(end1) > target1)
// end को डिक्रीमेंट करता है
end1--;
if (a2.get(start1) + a2.get(end1) < target1)
// start को इंक्रीमेंट करता है
start1++;
}
System.out.println("ऐसे मान नहीं मिले!");
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);
}
} आउटपुट
जोड़ी मिली: 13 + 21 = 34