मान लीजिए हमारे पास एक संतुलित बाइनरी सर्च ट्री (BST) और एक लक्ष्य योग है, हमें एक ऐसी विधि परिभाषित करनी है जो जांचे कि क्या इसमें कोई ऐसी जोड़ी मौजूद है जिसका योग लक्ष्य योग के बराबर हो। ध्यान रखें कि बाइनरी सर्च ट्री अपरिवर्तनीय (immutable) है।
उदाहरण के लिए, यदि इनपुट इस तरह का है:

तो आउटपुट होगा (9 + 26 = 35)
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- दो स्टैक s1, s2 परिभाषित करें
- done1 := false, done2 := false
- val1 := 0, val2 := 0
- curr1 := root, curr2 := root
- अनंत लूप में, निम्न कार्य करें:
- जब done1 false हो:
- यदि curr1 NULL नहीं है, तो:
- curr1 को s1 में डालें
- curr1 := curr1 का बायां बच्चा
- अन्यथा:
- यदि s1 खाली है, तो done1 := true
- अन्यथा:
- curr1 := s1 का शीर्ष तत्व
- s1 से तत्व हटाएं
- val1 := curr1 का मान
- curr1 := curr1 का दायां बच्चा
- done1 := true
- यदि curr1 NULL नहीं है, तो:
- जब done2 false हो:
- यदि curr2 NULL नहीं है, तो:
- curr2 को s2 में डालें
- curr2 := curr2 का दायां बच्चा
- अन्यथा:
- यदि s2 खाली है, तो done2 := true
- अन्यथा:
- curr2 := s2 का शीर्ष तत्व
- s2 से तत्व हटाएं
- val2 := curr2 का मान
- curr2 := curr2 का बायां बच्चा
- done2 := true
- यदि curr2 NULL नहीं है, तो:
- यदि val1 ≠ val2 और (val1 + val2) लक्ष्य के बराबर है, तो:
- जोड़ी प्रिंट करें (val1 + val2 = लक्ष्य)
- true लौटाएं
- अन्यथा जब (val1 + val2) < लक्ष्य, तो done1 := false
- अन्यथा जब (val1 + val2) > लक्ष्य, तो done2 := false
- यदि val1 ≥ val2, तो false लौटाएं
- जब done1 false हो:
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; #define MAX_SIZE 100 class TreeNode { public: int val; TreeNode *left, *right; TreeNode(int data) { val = data; left = NULL; right = NULL; } }; bool isPairPresent(TreeNode* root, int target) { stack<TreeNode*> s1, s2; bool done1 = false, done2 = false; int val1 = 0, val2 = 0; TreeNode *curr1 = root, *curr2 = root; while (true) { while (done1 == false) { if (curr1 != NULL) { s1.push(curr1); curr1 = curr1->left; } else { if (s1.empty()) done1 = 1; else { curr1 = s1.top(); s1.pop(); val1 = curr1->val; curr1 = curr1->right; done1 = 1; } } } while (done2 == false) { if (curr2 != NULL) { s2.push(curr2); curr2 = curr2->right; } else { if (s2.empty()) done2 = 1; else { curr2 = s2.top(); s2.pop(); val2 = curr2->val; curr2 = curr2->left; done2 = 1; } } } if ((val1 != val2) && (val1 + val2) == target) { cout << "Pair Found: " << val1 << " + " << val2 << " = " << target << endl; return true; } else if ((val1 + val2) < target) done1 = false; else if ((val1 + val2) > target) done2 = false; if (val1 >= val2) return false; } } int main() { TreeNode* root = new TreeNode(16); root->left = new TreeNode(11); root->right = new TreeNode(21); root->left->left = new TreeNode(9); root->left->right = new TreeNode(13); root->right->left = new TreeNode(17); root->right->right = new TreeNode(26); int target = 35; cout << (isPairPresent(root, target)); } इनपुट
TreeNode* root = new TreeNode(16); root->left = new TreeNode(11); root->right = new TreeNode(21); root->left->left = new TreeNode(9); root->left->right = new TreeNode(13); root->right->left = new TreeNode(17); root->right->right = new TreeNode(26);
आउटपुट
Pair Found: 9 + 26 = 35 1