# Binary Search Tree

Binary Seach Tree is the special type of node-based Binary Tree that contains data in an organized way so that basic operations such as insertion, deletion, and searching become easier. It is an ordered and sorted Binary Tree. A binary search tree in the data structure is the most interesting topic to learn. Let us see the implementation of the binary search tree and various operations on it. we will implement BST in the recursive algorithm.

## Properties of Binary Search Tree

- Tree Should be a Binary Tree
- Left Subtree Contains a value lower than the parent's value.
- Right Subtree Contains the value greater or equals to the parent's value.

Here is an

*Example of Binary search tree*## Application of Binary search tree

- A binary search tree is used in the implementation of searching algorithms
- A binary search tree is used in Multilevel indexing in a database.
- It is used in the Implementation of TreeMap and TreeSet
- It is used in data compression
- It is helpful in managing memory
- Searching in a Binary search tree is much easier than any other data structure.

## Basic Operations on Binary Search Tree (BST)

- INSERTION
- DELETION
- SEARCHING
- MODIFYING
- TRANSVERSAL

#### The requirement to learn Binary search tree

These are the topic that you should learn before understanding the binary search trees.

- Recursion
- Classes
- Node

### INSERTION in Binary Search Tree

Element in Binary Search Tree is Inserted on behalf of some rules which is mentioned earlier. Insertion means adding a new node in the Binary search tree.

Implementation of Binary search tree in Java is similar to another language as C++ and Python

Let us write code for making Node

the complexity of insertion in the Binary search tree is logN.

__Code for Node Creation in C++__ class Node

{

public:

int data;

Node* left;

Node* right;

Node(int val)

{

data=val;

left=NULL;

right=NULL;

}

};

__Code for Node creation in Java__class Node

{

int data;

Node left;

Node right;

public Node(int val)

{

data=val;

left=null;

right=null;

}

}

## Insertion in Binary Search Tree

we will make an Insert function to insert an element in the Binary Search Tree at its appropriate position. we will recursively iterate through either left or right of the root node to find its appropriate position for insertion.

#### Insertion in Binary search tree in C++

Node* inserts(Node* root, int val)

{

if(root==NULL)

{

Node* a = new Node(val);

root=a;

return root;

}

else if(val<root->data)

{

root->left=inserts(root->left,val);

}

else

{

root->right=inserts(root->right,val);

}

return root;

}

#### Insertion in Binary Search Tree in Java

Node insert(Node root, int val)

{

if(root==null)

{

root=new Node(val);

return root;

}

if(val<root.val)

{

root.left=insert(root.left,val);

}

else

{

root.right=insert(root.right,val);

}

return root;

}

#### InOrder Transversal in Binary Search Tree

In order transversal in Binary Search Tree gives elements in Ascending order. In this left subtree is visited first and then the right tree for accessing elements of all nodes.

__Code in C++__

void Inorder(Node* root)

{

Node* temp=root;

if(temp==NULL) return;

Inorder(root->left);

cout<<temp->data<<"\n";

Inorder(root->right);

}

__Code in Java__

void Inorder(Node* root)

{

Node* temp=root;

if(temp==NULL) return;

Inorder(root->left);

cout<<temp->data<<"\n";

Inorder(root->right);

}

We have discussed the Insertion of data in Binary Search Tree (BST) and Inorder Transversal in Binary search Tree. One of the major

**disadvantages of a Binary search tree**is that it requires a recursive approach for its implementation which is sometimes more complex to write. we prefer Binary Search Over any Other Data Structure because it is very efficient and less complex to perform basic operations such as searching and deletion. In Further Blogs, we will discuss How to Delete elements from the Binary Search tree. This is a very important topic for coding interviews and competitive programming.