C++ प्रोग्राम: जांचें कि दिया गया ट्री बाइनरी सर्च ट्री है या नहीं

बाइनरी सर्च ट्री एक बाइनरी ट्री डेटा स्ट्रक्चर है जिसमें 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(4); // 4, 6 के राइट में है लेकिन 7 से कम है - OK
    // लेकिन 4, 6 के राइट चाइल्ड के रूप में है, और 6, 7 का लेफ्ट है
    // तो 4, 7 के लेफ्ट सबट्री में है - OK
    // रुकिए, यह वास्तव में BST है! आइए चेक करें...
    
    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 है

सुधार: मूल आर्टिकल का पहला टेस्ट केस आउटपुट गलत था। ट्री 1 वास्तव में एक वैध BST है। आइए एक वास्तविक नॉन-BST उदाहरण देखें:

सही टेस्ट केस

// नॉन-BST उदाहरण: 7 के लेफ्ट सबट्री में 8 है (7 से बड़ा!)
n* root = newN(7);
root->l = newN(6);
root->r = newN(10);
root->l->l = newN(2);
root->l->r = newN(8); // 8 > 7 लेकिन लेफ्ट सबट्री में - BST नियम उल्लंघन!

if (isBST(root))
    cout << "BST है";
else
    cout << "BST नहीं है"; // यह प्रिंट होगा

एल्गोरिदम व्याख्या

• प्रत्येक नोड के लिए मान्य रेंज [min, max] बनाए रखें
• रूट के लिए: [INT_MIN, INT_MAX]
• लेफ्ट चाइल्ड के लिए: [min, parent->data - 1]
• राइट चाइल्ड के लिए: [parent->data + 1, max]
• यदि कोई नोड अपनी रेंज से बाहर है → BST नहीं

डुप्लीकेट मानों के लिए

यदि डुप्लीकेट अनुमत हैं (लेफ्ट में ≤ या राइट में ≥):

return BSTUtil(node->l, min, node->d) && BSTUtil(node->r, node->d, max);

समय जटिलता

• O(n) - प्रत्येक नोड एक बार विजिट होता है
• स्पेस: O(h) - रिकर्सन स्टैक, h = ट्री की ऊंचाई