हमारे पास एक सरणी A है, हमें जांचना है कि सरणी n लेवल के BST को दर्शा सकती है या नहीं। चूंकि लेवल n है, हम निम्न तरीके से ट्री बना सकते हैं। मान लीजिए एक संख्या k है, k से बड़ा मान दाईं ओर जाता है, और k से छोटा मान बाईं ओर जाता है। मान लीजिए दो सूचियां हैं: {50, 20, 9, 25, 10}, और {50, 30, 20, 25, 10}

पहली वैध नहीं है, लेकिन दूसरी वैध है।
इसे जांचने के लिए हम या तो BST बना सकते हैं और ऊंचाई जांच सकते हैं, अन्यथा सरणी-आधारित दृष्टिकोण का उपयोग कर सकते हैं। सरणी-आधारित दृष्टिकोण नीचे जैसा है -
- दो वेरिएबल लें max = इन्फिनिटी, बाएं सबट्री की अधिकतम सीमा चिह्नित करने के लिए, और min = नेगेटिव इन्फिनिटी दाएं सबट्री के लिए न्यूनतम सीमा चिह्नित करने के लिए
- arr[i] से arr[n-1] रेंज में प्रत्येक तत्व के लिए, निम्न चरण दोहराएं
- यदि arr[i] > arr[i-1] और arr[i] > min और arr[i] < max, तो min := arr[i-1] अपडेट करें
- अन्यथा यदि arr[i] > min और arr[i] < max, तो max := arr[i] अपडेट करें
- यदि इनमें से कोई भी वैध नहीं है, तो तत्व एक नए लेवल में डाला जाएगा, तो ब्रेक करें
उदाहरण
#include <iostream> using namespace std; bool canMakeBSTifHeightN(int arr[], int n) { int min = INT_MIN; int max = INT_MAX; for(int i = 1; i < n; i++){ if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) { min = arr[i - 1]; } else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) { max = arr[i - 1]; } else { return true; } } return false; } int main() { int elements[] = {50, 30, 20, 25, 10}; int n = sizeof(elements)/sizeof(elements[0]); if (canMakeBSTifHeightN(elements, n)) cout << "We can make BST of height " << n; else cout << "We can not make BST of height " << n; }आउटपुट
We can make BST of height 5