BST

#include <iostream>
#include <queue>

using namespace std;
struct Node{
    int data ;
    Node* left;
    Node* right;
};


// Creation of Node
Node *createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}


// Insertion of Node in BST
Node* Insert(Node *root, int data){
    
    if(root==NULL){
        root=createNode(data);
    }
    else if(data<root->data){
        root->left = Insert(root->left,data);
    }
    else
        root->right = Insert(root->right,data);
    return root;
}


// Searching of data in BST
Node* searchNode(Node* root, int value){
    
    if(root==NULL){
        return NULL;
    }
    
    else if(root->data == value){
        return root;
    }
    
    else if(value<root->data){
        return searchNode(root->left,value);
    }
    
    else return searchNode(root->right,value);
    
}




// void deleteNode(Node*root , int data){
    
    
//     if(root==NULL){
//         cout<<"Tree is already Empty";
//     }
    
    
    
    
    
    
// }



// Level order Traversal of BST
void levelOrderPrint(Node * root) {
    
    if(root==NULL){
        return;
    }
    queue<Node *> q;
    q.push(root);
    
    while(!q.empty()){
        Node* current = q.front();
        cout<<current->data<<" ";
        if(current->left !=NULL) q.push(current->left);
        if(current->right != NULL) q.push(current->right);
        q.pop();
    }
}

// Inorder Traversal
void inorderTraversal (Node *root){
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout<<root->data<<" ";
    inorderTraversal(root->right);
}

// Preorder Traversal
void preorderTraversal (Node *root){
    if(root == NULL)
        return;
    cout<<root->data<<" ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// Postorder Traversal
void postorderTraversal (Node *root){
    if(root == NULL)
        return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout<<root->data<<" ";
}


// Check whether a given tree is BST or Not
bool check(Node *root){
    
    
    if(root==NULL){
        return true;
    }
    
    if(root->left == NULL && root->right == NULL){
        return true;    
    }
    
    
    Node *current = root->left;
    while(current->right !=NULL){
        current = current->right;
    }
    int min = current->data;
    
    Node *max = root->right;
    while(max->left !=NULL){
        max = max->left;
    }
    int maxi = max->data;
    
    if(root->data > min && root->data < maxi){
        return true;
    }
    
    return false;
}

// Find Min value in a BST
int min(Node *root) {
    
    if(root==NULL){
        return 0;
    }
    
    Node * current = root;
    while(current->left != NULL){
        current = current->left;
    }
    
    return current->data;
    
}

// Find Max value in a BST
int max(Node *root) {
    
    if(root==NULL){
        return 0;
    }
    
    Node * current = root;
    while(current->right != NULL){
        current = current->right;
    }
    
    return current->data;
    
}



int main() {
    Node* root = NULL;
    root = Insert(root,10);
    root = Insert(root,9);
    root = Insert(root,15);
    root = Insert(root,8);
    root = Insert(root,17);
    
    // cout<<searchNode(root,10);
    // cout<<endl;
    // cout<<root;
    levelOrderPrint(root);
    cout<<endl;
    inorderTraversal(root);
    cout<<endl;
    preorderTraversal(root);
    cout<<endl;
    postorderTraversal(root);
    cout<<endl;
    cout<<check(root);
    cout<<endl;
    cout<<min(root);
    cout<<endl;
    cout<<max(root);    
    
    
}