बाइनरी सर्च ट्री एक बाइनरी ट्री डेटा स्ट्रक्चर है जिसमें 3 गुण होते हैं:
- बाइनरी सर्च ट्री के नोड का लेफ्ट सबट्री केवल उन नोड्स को समाहित करता है जिनकी कीज़ नोड की की से कम होती हैं
- बाइनरी सर्च ट्री नोड का राइट सबट्री केवल उन नोड्स को समाहित करता है जिनकी कीज़ नोड की की से अधिक होती हैं
- सबट्री का लेफ्ट और राइट प्रत्येक एक बाइनरी सर्च ट्री होना चाहिए
एल्गोरिदम
शुरुआत
function BSTUtil()
यदि नोड NULL के बराबर है तो
1 लौटाएं
यदि नोड का डेटा न्यूनतम से कम या अधिकतम से अधिक है तो
0 लौटाएं
लेफ्ट और राइट सब-ट्रीज को रिकर्सिवली ट्रैवर्स करें
समाप्तिउदाहरण कोड
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
struct n {
int d;
n* l;
n* r;
};
int BSTUtil(n* node, int min, int max);
int isBST(n* node) {
return BSTUtil(node, INT_MIN, INT_MAX);
}
int BSTUtil(struct n* node, int min, int max) {
if (node == NULL)
return 1;
if (node->d < min || node->d > max)
return 0;
return BSTUtil(node->l, min, node->d - 1) && BSTUtil(node->r, node->d + 1, max);
}
n* newN(int d) {
n* nod = new n;
nod->d = d;
nod->l = NULL;
nod->r = NULL;
return nod;
}
int main() {
// टेस्ट 1: BST नहीं (सही उदाहरण)
n* root = newN(7);
root->l = newN(6);
root->r = newN(10);
root->l->l = newN(2);
root->l->r = newN(8); // 8 > 7 लेकिन लेफ्ट सबट्री में - उल्लंघन!
if (isBST(root))
cout << "दिया गया बाइनरी ट्री एक BST है" << endl;
else
cout << "दिया गया बाइनरी ट्री BST नहीं है" << endl;
// टेस्ट 2: BST है
n* root1 = newN(10);
root1->l = newN(6);
root1->r = newN(11);
root1->l->l = newN(2);
root1->l->r = newN(7);
if (isBST(root1))
cout << "दिया गया बाइनरी ट्री एक BST है" << endl;
else
cout << "दिया गया बाइनरी ट्री BST नहीं है" << endl;
return 0;
}आउटपुट
दिया गया बाइनरी ट्री BST नहीं है
दिया गया बाइनरी ट्री एक BST हैनोट: यह आर्टिकल 1005082699 के समान है। दोनों एक ही विषय पर हैं। मूल आर्टिकल 1005082699 में पहले टेस्ट केस का आउटपुट गलत था (यह BST था लेकिन "नहीं है" प्रिंट किया गया था)। यहां सही टेस्ट केस दिया गया है।
वैकल्पिक दृष्टिकोण: इनऑर्डर ट्रैवर्सल
bool isBST_Inorder(n* root) {
static n* prev = NULL;
if (root) {
if (!isBST_Inorder(root->l)) return false;
if (prev != NULL && root->d <= prev->d) return false;
prev = root;
return isBST_Inorder(root->r);
}
return true;
}
यह दृष्टिकोण BST के गुण का उपयोग करता है: इनऑर्डर ट्रैवर्सल सॉर्टेड क्रम देता है।
समय जटिलता
- O(n) - दोनों दृष्टिकोण
- स्पेस: O(h) - रिकर्सन स्टैक
