जांचें कि क्या दिया गया सरणी सी ++ में बाइनरी सर्च ट्री के प्रीऑर्डर ट्रैवर्सल का प्रतिनिधित्व कर सकता है

मान लीजिए कि हमारे पास एक सरणी में तत्वों की एक सूची है, हमें यह जांचना होगा कि क्या तत्व बाइनरी सर्च ट्री का प्रीऑर्डर ट्रैवर्सल हो सकता है या नहीं। मान लीजिए कि एक क्रम {40, 30, 35, 80, 100} जैसा है, तो पेड़ जैसा होगा -

हम इसे एक स्टैक का उपयोग करके हल कर सकते हैं। इस समस्या को हल करने के लिए हमें इन चरणों का पालन करना होगा।

• खाली स्टैक परिभाषित करें
• रूट को ऋणात्मक अनंत के रूप में सेट करें
• पूर्व-आदेश क्रम में प्रत्येक तत्व के लिए, निम्न कार्य करें -
  • यदि तत्व वर्तमान रूट से छोटा है, तो झूठी वापसी करें
  • तत्वों को स्टैक से हटाते रहें, जबकि तत्व स्टैक टॉप से ​​बड़ा है, और अंतिम रूप से हटाए गए तत्व को रूट के रूप में बनाएं।
  • तत्व को स्टैक में पुश करें

उदाहरण

#include <iostream>
#include <stack>
using namespace std;
bool isValidPreorder(int pre[], int n) {
   stack<int> 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 can not form BST";
}

आउटपुट

This can form BST