check_bst_or_not.cpp

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

struct Node {
    int data;
    Node *left, *right;

    Node(int val) {
        data = val;
        left = NULL;
        right = NULL;
    }
};

bool isBST(Node* root, Node* min=NULL, Node* max=NULL) {
    if(root == NULL) {
        return true;
    }

    if(min != NULL && root->data <= min->data) {
        return false;
    }

    if(max != NULL && root->data >= max->data) {
        return false;
    }

    bool leftValid = isBST(root->left, min, root);
    bool rightValid = isBST(root->right, root, max);

    return (leftValid && rightValid);
}


int main() {

    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    
    if(isBST(root, NULL, NULL)) {
        cout<<"Valid BST"<<endl;
    } else
    {
        cout<<"Invalid BST"<<endl;
    }
    
    Node* root2 = new Node(5);
    root2->left = new Node(2);
    root2->right = new Node(8);
    
    if(isBST(root2, NULL, NULL)) {
        cout<<"Valid BST"<<endl;
    } else
    {
        cout<<"Invalid BST"<<endl;
    }
    
    return 0;
}