#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);
}
