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

एक बाइनरी ट्री एक ट्री डेटा संरचना है जिसमें प्रत्येक नोड के लिए दो चाइल्ड नोड्स होते हैं। चाइल्ड नोड्स दो होने के कारण इन्हें लेफ्ट और राइट चाइल्ड कहा जाता है।

BST एक ट्री संरचना है जिसमें लेफ्ट सबट्री में रूट से कम मान वाले नोड्स होते हैं और राइट सबट्री में रूट से अधिक मान वाले नोड्स होते हैं।

यहां, हम जांचेंगे कि क्या एक बाइनरी ट्री BST है या नहीं।

इसकी जांच के लिए हमें बाइनरी ट्री पर BST कंडीशन की जांच करनी होगी। एक रूट नोड के लिए जांचें कि लेफ्ट चाइल्ड रूट से कम होना चाहिए, राइट चाइल्ड रूट से अधिक होना चाहिए, उन सभी नोड्स के लिए जिनमें चाइल्ड्स मौजूद हैं।

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

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

int isBSTUtil(Node* node, int min, int max);
int isBST(Node* node) {
    return isBSTUtil(node, INT_MIN, INT_MAX);
}

int isBSTUtil(Node* node, int min, int max) {
    if (node == NULL)
        return 1;
    if (node->data < min || node->data > max)
        return 0;
    return isBSTUtil(node->left, min, node->data - 1) &&
           isBSTUtil(node->right, node->data + 1, max);
}

int main() {
    Node* root = new Node(8);
    root->left = new Node(3);
    root->right = new Node(10);
    root->left->left = new Node(1);
    root->left->right = new Node(6);
    if (isBST(root))
        cout << "The given tree is a BST";
    else
        cout << "The given tree is Not a BST";
    return 0;
}

आउटपुट

The given tree is a BST

कोड व्याख्या

उपरोक्त कोड BST की जांच करता है। मुख्य विधि एक ट्री बनाती है और isBST() मेथड कॉल करती है। यह मेथड जांचता है कि लेफ्ट और राइट चाइल्ड BST नियम का पालन करते हैं और यह भी कि बने सबट्री भी BST हैं, isBSTUtil() मेथड का उपयोग करके।