C++-এ Verify Preorder Sequence in BST: প্রি-অর্ডার সিকোয়েন্স BST-র নাকি যাচাই করা

একটি সংখ্যা সিকোয়েন্স দেওয়া আছে। এটি একটি বাইনারি সার্চ ট্রির (BST) সঠিক প্রি-অর্ডার ট্রাভার্সাল সিকোয়েন্স কিনা তা যাচাই করতে হবে। সিকোয়েন্সের সব সংখ্যা ইউনিক।

উদাহরণ

ইনপুট: [5,2,1,3,6]

আউটপুট: true

সমাধানের পদ্ধতি (Stack Simulation / Monotonic Stack)

itr = -1 (স্ট্যাক পয়েন্টার), low = INT_MIN (ন্যূনতম অনুমোদিত ভ্যালু)।
প্রি-অর্ডার সিকোয়েন্স ট্রাভার্স করুন i = 0 থেকে n-1:
- x = preorder[i]।
- যদি x < low, তবে ইনভ্যালিড → false রিটার্ন করুন (কারণ BST-এ ডান সাবট্রিতে সব ভ্যালু > প্যারেন্ট)।
- while (itr >= 0 && preorder[itr] < x):
  - low = preorder[itr] (পপ করা এলিমেন্টগুলো প্যারেন্ট, যাদের ডান সাবট্রিতে এসে আছি)۔
  - itr-- (স্ট্যাক পপ)।
- itr++, preorder[itr] = x (কারেন্ট এলিমেন্ট স্ট্যাকে পুশ)۔
লুপ শেষ হলে true রিটার্ন করুন।

এই ইন-প্লেস স্ট্যাক সিমুলেশন O(n) টাইম এবং O(1) এক্সট্রা স্পেসে কাজ করে।

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

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

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int itr = -1;
        int low = INT_MIN;
        for (int i = 0; i < preorder.size(); i++) {
            int x = preorder[i];
            if (x < low) return false;
            while (itr >= 0 && preorder[itr] < x) {
                low = preorder[itr];
                itr--;
            }
            itr++;
            preorder[itr] = x;
        }
        return true;
    }
};

int main() {
    Solution ob;
    vector<int> v = {5,2,1,3,6};
    cout << (ob.verifyPreorder(v));
    return 0;
}

ইনপুট

{5,2,1,3,6}