C++ में सरणी BST के प्रीऑर्डर ट्रैवर्सल को दर्शा सकती है या नहीं जांचें

समस्या विवरण

एक सरणी दी गई है, जांचें कि क्या यह किसी BST का वैध प्रीऑर्डर ट्रैवर्सल हो सकती है।

उदाहरण: {40, 30, 35, 80, 100} → वैध BST प्रीऑर्डर

एल्गोरिदम (स्टैक का उपयोग)

1. खाली स्टैक और root = INT_MIN
2. प्रत्येक तत्व के लिए:
   • यदि तत्व < root → false
   • जब तक स्टैक खाली नहीं और तत्व > स्टैक टॉप: स्टैक से पॉप करें, अंतिम पॉप किया गया root बने
   • तत्व को स्टैक में पुश करें
3. अंत में true

उदाहरण कोड

#include <iostream>
#include <stack>
#include <climits>
using namespace std;

bool isValidPreorder(int pre[], int n) {
    stack stk;
    int root = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        if (pre[i] < root) return false;
        while (!stk.empty() && stk.top() < pre[i]) {
            root = stk.top();
            stk.pop();
        }
        stk.push(pre[i]);
    }
    return true;
}

int main() {
    int pre[] = {40, 30, 35, 80, 100};
    int n = sizeof(pre)/sizeof(pre[0]);
    if (isValidPreorder(pre, n))
        cout << "This can form BST";
    else
        cout << "This cannot form BST";
    return 0;
}

आउटपुट

This can form BST