Binary Search Tree
Binary Search Tree is a special type of binary tree that has a specific order of elements in it. Every node in a binary search tree has a unique value. As it is a binary tree, each tree node has maximum of two children.
A Binary Search Tree is used to search a number in
O(log(n))
time.
Properties of Binary Search Tree

All nodes in the left subtree have a lower value than the root node's value.

All nodes in the right subtree have a higher value than the root node’s value

The left and right subtrees must also be binary search trees i.e. , they must follow the above two properties.

Inorder traversal of Binary Search Tree returns a sorted arrangement of its values
Operations on Binary Search Tree
Searching
Binary Search Tree has special properties which can be used to efficiently search for an element, unlike in normal Binary Tree where the entire tree needs to be traversed(worst case scenario)
While comparing the value of the item that needs to be searched with the root of the tree, there are three possibilities :
val == root→data
item is found, stop the operation.val > root→data
Check only the right subtree since all the values in the left subtree are lesser thanroot→data
val < root→data
Check only the left subtree as all values in the right subtree are greater thanroot→data
Performing this operation recursively decreases the search time complexity as only one subtree has to be traversed.
Code
I. Recursive Technique :
node* Search(node* root, int val) { if (val == NULL) return NULL; if (val == root>data) return root>data; if (val < root>data) return Search(root>left, val); if (val > root>data) return Search(root>right, val);
II. Iterative Technique :
node* Search(node* node, int val)
{
while(node)
{
if (val == node>data)
return node>data;
if (val < root>data)
node = node>left;
else
node = node>right;
}
return NULL;
}
Insertion
To insert a node in a Binary Search Tree :
 if root is NULL, create a new node and store value in it.
 else, compare value with data in root node.
 If
val > root→data
, recurse for right subtree  If
val < root→data
, recurse for left subtree
 If
node insert(node root, val)
{
if ( root == NULL )
{
root = node(val)
return root
}
if (root>data < val)
root>right = insert(root>right, val)
else if (root>data > val)
root>left = insert(root>left, val)
return root
}