दो BSTs से योग x वाले नोड जोड़ों की गणना - C++

समस्या विवरण

हमें दो बाइनरी सर्च ट्री (BST) और एक मान x दिया गया है। लक्ष्य उन नोड जोड़ों की गणना करना है जहाँ एक नोड पहले BST से और दूसरा दूसरे BST से हो, और उनके डेटा का योग x के बराबर हो।

उदाहरण

आउटपुट: 1 (जोड़ी: 8+6=14)

आउटपुट: 2 (जोड़ियाँ: 5+15=20, 4+16=20)

दृष्टिकोण

पहले BST को इनऑर्डर (छोटे से बड़े) और दूसरे को रिवर्स इनऑर्डर (बड़े से छोटे) में पुनरावृत्त करें। दो स्टैक का उपयोग करें। वर्तमान नोड्स का योग x से तुलना करें:

• sum == x: गणना बढ़ाएँ, दोनों स्टैक से पॉप करें, अगले नोड्स पर जाएँ
• sum < x: पहले BST से अगला बड़ा नोड लें
• sum > x: दूसरे BST से अगला छोटा नोड लें

एल्गोरिदम

1. दोनों BSTs के रूट नोड्स लें
2. दो स्टैक stack_1, stack_2 बनाएँ
3. बाहरी लूप में:
   • BST_1 के बाएँतम नोड तक जाएँ, सभी को stack_1 में पुश करें
   • BST_2 के दाएँतम नोड तक जाएँ, सभी को stack_2 में पुश करें
   • यदि कोई स्टैक खाली है तो ब्रेक करें
   • दोनों टॉप नोड्स का योग temp में लें
   • temp के अनुसार गणना अपडेट करें और पॉप/नेविगेट करें
4. गणना लौटाएँ

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

struct Tree {
    int data;
    Tree *left, *right;
    Tree(int d) : data(d), left(nullptr), right(nullptr) {}
};

Tree* insert_node(int data) {
    return new Tree(data);
}

int BST_sum_x(Tree* BST_1, Tree* BST_2, int x) {
    int count = 0;
    stack stack_1, stack_2;
    
    if (!BST_1 || !BST_2) return 0;
    
    while (true) {
        while (BST_1) { stack_1.push(BST_1); BST_1 = BST_1->left; }
        while (BST_2) { stack_2.push(BST_2); BST_2 = BST_2->right; }
        
        if (stack_1.empty() || stack_2.empty()) break;
        
        Tree* top1 = stack_1.top();
        Tree* top2 = stack_2.top();
        int sum = top1->data + top2->data;
        
        if (sum == x) {
            count++;
            stack_1.pop(); stack_2.pop();
            BST_1 = top1->right;
            BST_2 = top2->left;
        } else if (sum < x) {
            stack_1.pop();
            BST_1 = top1->right;
        } else {
            stack_2.pop();
            BST_2 = top2->left;
        }
    }
    return count;
}

int main() {
    Tree* BST_1 = insert_node(15);
    BST_1->left = insert_node(10);
    BST_1->right = insert_node(8);
    BST_1->left->left = insert_node(12);
    BST_1->left->right = insert_node(24);
    BST_1->right->left = insert_node(16);
    
    Tree* BST_2 = insert_node(20);
    BST_2->left = insert_node(16);
    BST_2->right = insert_node(4);
    BST_2->left->left = insert_node(18);
    BST_2->left->right = insert_node(28);
    BST_2->right->left = insert_node(22);
    
    int x = 28;
    cout << "Count: " << BST_sum_x(BST_1, BST_2, x);
    return 0;
}

आउटपुट

Count: 1