## 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:

- For every node X(root).
- All the keys in its left subtree are smaller than the key value in X(root).
- 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.

__Operations performed on BST:__

**Searching.****Insertion.**

__Searching BST__

__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

**{**

**root = AddNewNode(data);**

**}**

**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* AddNewNode(int data) {

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

root = AddNewNode(data);

}

// 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";

else cout<<"Not Found\n";

}

So, we have come to an end of this article. I hope you guys liked this article.

Here are some articles you people may like:

## 0 Comments