//
//  main.cpp
//  Binary Search Tree (Basic)
//
//  Created by Himanshu on 16/09/21.
//

#include <iostream>
using namespace std;

struct node {
    int info = 0;
    struct node *left, *right;
};
typedef struct node Node;

node* newNode(int data)
{
    node* Node = new node();
    Node->info = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return(Node);
}

Node* insert (Node *root, int n) {
    if (root == NULL) {
        root = newNode(n);
    } else {
        if (root->info > n) {
            root->left = insert (root->left, n);
        } else {
            root->right = insert (root->right, n);
        }
    }
    return root;
}

Node* search (Node *root, int n) {
    if (root == NULL || root->info == n) {
        return root;
    } else {
        if (root->info > n) {
            return search (root->left, n);
        } else {
            return search (root->right, n);
        }
    }
}

int main() {
    Node *root = newNode(5);
    insert(root, 3);
    insert(root, 2);
    insert(root, 4);
    insert(root, 7);
    
    //Searching 4 in the tree
    if (search (root, 4)) {
        cout<<"4 is present in the BST"<<endl;
    } else {
        cout<<"4 is not in the BST"<<endl;
    }

    //Searching 8 in the tree
    if (search (root, 8)) {
        cout<<"8 is present in the BST"<<endl;
    } else {
        cout<<"8 is not in the BST"<<endl;
    }
    
    return 0;
}