ব্যালেন্সড BST-এ দেওয়া সমের সাথে একটি জোড়া খুঁজে বের করা C++-তে

সমস্যা বিবরণ

ধরা যাক আমাদের একটি ব্যালেন্সড বাইনারি সার্চ ট্রি (BST) এবং একটি লক্ষ্য সম (target sum) আছে। আমাদের একটি পদ্ধতি সংজ্ঞায়িত করতে হবে যা যাচাই করবে যে ট্রিতে এমন কোনো জোড়া নোড আছে কিনা যাদের মানগুলোর যোগফল লক্ষ্য সমের সমান। এই সমস্যার একটি গুরুত্বপূর্ণ সীমাবদ্ধতা হল বাইনারি সার্চ ট্রিটি অপরিবর্তনীয় (immutable)।

উদাহরণ

ইনপুট ট্রি:

লক্ষ্য সম = 35, আউটপুট হবে (9 + 26 = 35)

সমাধানের পদ্ধতি

এই সমস্যাটি সমাধান করার জন্য আমরা দুটি স্ট্যাক ব্যবহার করব: একটি ইনঅর্ডার ট্রাভার্সালের জন্য (সর্বোচ্চ থেকে সর্বনিম্ন) এবং অন্যটি রিভার্স ইনঅর্ডার ট্রাভার্সালের জন্য (সর্বনিম্ন থেকে সর্বোচ্চ)। এটি দ্বি-পอยেন্টার কৌশলের সমানांतর।

1. দুটি স্ট্যাক সংজ্ঞায়িত করুন: s1 (ইনঅর্ডার용) এবং s2 (রিভার্স ইনঅর্ডার용)।
2. বুলিয়ান ভেরিয়েবল: done1 = false, done2 = false।
3. মানের ভেরিয়েবল: val1 = 0, val2 = 0।
4. বর্তমান নোড পয়েন্টার: curr1 = root, curr2 = root।
5. অবিরত লুপ চলান:
   • ইনঅর্ডার ট্রাভার্সাল (s1): সবচেয়ে ছোট মান পাওয়া পর্যন্ত বাম শাখায় যান।
   • রিভার্স ইনঅর্ডার ট্রাভার্সাল (s2): সবচেয়ে বড় মান পাওয়া পর্যন্ত ডান শাখায় যান।
   • প্রাপ্ত দুটি মান (val1, val2) তুলনা করুন:
     • যদি val1 != val2 এবং val1 + val2 == target হয়, তবে জোড়া পাওয়া গেছে। প্রিন্ট করে true রিটার্ন করুন।
     • যদি যোগফল target-এর চেয়ে ছোট হয়, তবে done1 = false করে পরবর্তী বড় মান আনুন।
     • যদি যোগফল target-এর চেয়ে বড় হয়, তবে done2 = false করে পরবর্তী ছোট মান আনুন।
     • যদি val1 >= val2 হয়, তবে আর জোড়া পাওয়া সম্ভব নেই, false রিটার্ন করুন।

C++ কোড উদাহরণ

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

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 = true;
                else {
                    curr1 = s1.top(); s1.pop();
                    val1 = curr1->val;
                    curr1 = curr1->right;
                    done1 = true;
                }
            }
        }

        // রিভার্স ইনঅর্ডার: বড় থেকে ছোট
        while (done2 == false) {
            if (curr2 != NULL) {
                s2.push(curr2);
                curr2 = curr2->right;
            } else {
                if (s2.empty()) done2 = true;
                else {
                    curr2 = s2.top(); s2.pop();
                    val2 = curr2->val;
                    curr2 = curr2->left;
                    done2 = true;
                }
            }
        }

        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));
    return 0;
}

আউটপুট

Pair Found: 9 + 26 = 35
1