Binary Search Tree
 Search Operation on Binary Search Tree
 BST Search Algorithm
 BST Search Illustration
 Insertion in BST
 BST Insert Algorithm
 BST Insert Illustration
 BST Search & Insert Implementation
 BST Insert & Search Algorithm Complexity
Binary Search Tree (BST) is an ordered nodebased binary tree data structure. The nodes have a value and two child nodes(A binary tree has a maximum of two child nodes) left & right attached to it. Except for the root node, all nodes can be referenced only by their parent. A BST has the following properties:
 All nodes in the left subtree are smaller than the root node.
 All nodes in the right subtree are larger than the root node.
 The left and right subtrees must also be binary search trees.
The tree on the left satisfies all the properties of BST. On the other hand, the tree on the right side seems to be a BST as all nodes in the left subtree are smaller and in the right subtree are larger. But Node
1
on the left subtree dissatisfies BST properties as it is smaller than Node4
but not greater than root node3
. Hence, it is not a BST.
Since it is an ordered data structure, the elements entered are always organized in a sorted fashion. We can use inorder traversal to retrieve the data stored in BST in sorted order. It gets its name because, just like binary search, it can be used to search the data in O(logn)
.
Search Operation on Binary Search Tree
We know that in a BST, all elements on the right side of the root are larger, and hence if the target element we are searching for is smaller than the root, the whole right subtree can be neglected. Similarly, if the element is larger than the root then the left subtree can be neglected. We move in a similar fashion until we exhaust the tree or find the target element as the subtree’s root. If the BST is balanced (A tree is called a balanced tree if for all nodes the difference between the height of the left and the right subtree is less than equal to 1.), then the search inside BST performs similar to binary search as both subtrees have around half of the elements which are neglected at every iteration but in case of an unbalanced tree all the nodes may be present on same side and search might perform similar to linear search.
BST Search Algorithm
Let root
be the root node of BST and X
be the target element being searched.

If
root
==NULL
, returnNULL
; 
If
X
==root>data
, returnroot
; 
If
X
<root>data
, returnsearch(root>left)

If
X
>root>data
, returnsearch(root>right)
BST Search Illustration
Suppose we have the above BST, and we want to find the element X
= 25
.

Compare the root element with
X
to find that41
>25
, so discard the right half and shift to the left subtree. 
The root of left subtree
23
<25
hence discard its left subtree and move to the right. 
The new root
28
<25
, so move toward the left and find our elementX
equals25
and return the node.
Insertion in BST
The algorithm to insert an element inside BST is pretty similar to searching an element inside BST because before inserting an element, we have to find its correct position. The only difference in insert and search function is that in case of search, we return the node containing the target value, whereas we create a new node at the node’s appropriate position in case of an insert.
BST Insert Algorithm
Let root
be the root node of BST and X
be the element we want to insert.

If
root
==NULL
, return a newly formed node withdata
=X

if (
X
<root>data
),root>left
=insert(root>left, X)
; 
else if (
X
>root>data
) ,root>right
=insert(root>right, X)
; 
return a pointer to the original
root
;
BST Insert Illustration

First, we initialize BST by creating a
root
node and insert5
in it. 
3
is smaller than5
so it gets inserted into the left of5
. 
4
is smaller than5
but large than3
so it gets inserted into the right of3
but left of4
. 
2
is the smallest element in the current tree, so it gets inserted at the leftmost position. 
1
is the smallest element in the current tree, so it gets inserted at the leftmost position. 
6
is the largest element in the current tree, so it gets inserted at the rightmost position.
This is how we insert elements inside a BST.
BST Search & Insert Implementation
#include <iostream>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node *newNode(int item) {
Node *temp = (Node *)malloc(sizeof(Node));
temp>key = item;
temp>left = temp>right = NULL;
return temp;
}
void inorder(Node *root) {
if (root != NULL) {
inorder(root>left);
cout << root>key << " ";
inorder(root>right);
}
}
Node *insert(Node *root, int key) {
if (root == NULL) return newNode(key);
if (key < root>key)
root>left = insert(root>left, key);
else
root>right = insert(root>right, key);
return root;
}
Node *search(Node *root, int key) {
if (root == NULL  root>key == key) return root;
if (root>key < key) return search(root>right, key);
return search(root>left, key);
}
int main() {
Node *root = NULL;
root = insert(root, 5);
root = insert(root, 3);
root = insert(root, 8);
root = insert(root, 6);
root = insert(root, 4);
root = insert(root, 2);
root = insert(root, 1);
root = insert(root, 7);
cout << search(root, 5)>key << endl;
}
BST Insert & Search Algorithm Complexity
Time Complexity
 Average Case
On averagecase, the time complexity of inserting a node or searching an element in a BST is of the order of height of binary search tree. On average, the height of a BST is O(logn)
. It occurs when the BST formed is a balanced BST. Hence the time complexity is of the order of [Big Theta]: O(logn)
.
 Best Case
The bestcase occurs when the tree is a balanced BST. The bestcase time complexity of insertion and searching is of the order of O(logn)
. It is the same as averagecase time complexity.
 Worst Case
In the worstcase, we might have to traverse from root to the deepest leaf node, i.e., the whole height h
of the tree. If the tree is unbalanced, i.e., it is skewed, the tree’s height may become n
, and hence the worstcase time complexity of both insert and search operation is O(n)
.
Space Complexity
The space complexity of both insert and search operation is O(n)
due to the space required by recursive calls.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedInRelated Article  Data Structure
 Circular Doubly Linked List
 Circular Linked List
 Doubly Linked List
 Linked List Deletion
 Linked List Insertion
 Linked List Merge Sort
Related Article  Binary Tree
 Convert Binary Tree to Binary Search Tree
 Binary Search Tree Check
 Binary Search Tree Inorder Succesor
 Binary Tree Traversal
 Binary Search Tree Delete