# Binary Search Tree

## Binary Search Trees

### What is a binary search tree(BST):

• A binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers in a tree data structure.
• To be a binary search tree first, the tree should satisfy all the properties of a binary tree.
• This binary search tree is a data structure for efficient searching, insertion, and deletion.
• Binary search tree properties:
1. For every node X(root).
2. All the keys in its left subtree are smaller than the key value in X(root).
3. All the keys in its right subtree are larger than the key value in X(root).
• In the above figure, the left tree is a binary search tree, whereas the right tree is not a binary search tree as it doesn't satisfy the properties of BST.

1. Searching.
2. Insertion.

### Searching BST

• If we are searching for a key that is equal to root, then we are done with searching.
• If we are searching for a key<root, then we must search in the left sub-tree.
• If we are searching for a key>root, then we must search in the right sub-tree.

Search for 10:
• Compare 10:5(root), as 10>5, go to right sub-tree.
• Compare  10:8, as 10>8, go to right sub-tree.
• Compare 10:9, as 10>9, go to the right sub-tree.
• Compare 10:11, as 10<11, go to left sub-tree.
• Compatre 10:10, 10=10, found it!.
Implementation of searching operation in c/c++:

bool search(struct node *root, int key)
{
if(root==NULL)//If the tree is empty
{
return false;
}
else if(key==root->data)//If the key is found at the root then return root.
{
return true;
}
else if(key < root->data)//If the key is less than the root node then search in left subtree.
{
return search(root->left,key);
}
else{
return search(root->right,key); //If the key is greater than the root node then search in right subtree.
}
}

### Insertion in BST

• If the tree is empty(root==NULL), then consider the new element as root.
• If the element is greater than the root, then insert the element to right sub-tree.
• If the element is less than the root, then insert the element to left sub-tree.

Implementation of insertion operation in c/c++:

BST* Insert(BST* root,int data) {
if(root == NULL) // empty tree
}
else if(data <= root->data) // if data to be inserted is lesser, insert in left subtree.
{
root->left = Insert(root->left,data);
}
else   // else, insert in right subtree.
{
root->right = Insert(root->right,data);
}
return root;
}

Binary search tree implementation:

// Binary Search Tree - Implemenation in C++
// Simple program to create a BST of integers and search an element in it
#include<iostream>
using namespace std;

//Definition of Node for Binary search tree
struct BST {
int data;
BST* left;
BST* right;
};

// Function to create a new Node in heap
BST* newNode = new BST();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

// To insert data in BST, returns address of root node
BST* Insert(BST* root,int data) {
if(root == NULL) { // empty tree
}

// if data to be inserted is lesser, insert in left subtree.
else if(data <= root->data) {
root->left = Insert(root->left,data);
}

// else, insert in right subtree.
else {
root->right = Insert(root->right,data);
}
return root;
}
//To search an element in BST, returns true if element is found
bool Search(BST* root,int data) {
if(root == NULL) {
return false;
}
else if(root->data == data) {
return true;
}
else if(data <= root->data) {
return Search(root->left,data);
}
else {
return Search(root->right,data);
}
}
int main() {
BST* root = NULL;  // Creating an empty tree
root = Insert(root,15);
root = Insert(root,10);
root = Insert(root,20);
root = Insert(root,25);
root = Insert(root,8);
root = Insert(root,12);
// Ask user to enter a number.
int number;
cout<<"Enter number be searched\n";
cin>>number;
//If number is found, print "FOUND"
if(Search(root,number) == true) cout<<"Found\n";