What is a Binary Search Tree?
In computer science, a binary search tree is an ordered data structure that is logically visualized as a tree with a single root node and has two children, one on its right side and the other on its left. These are known as the left child and right child. These children further make subtrees until they reach leaf nodes. It is also often referred to as an ordered binary tree or a sorted binary tree. In a sorted binary tree, the right child’s value is always more significant than the parent node’s value. Similarly, the value of the left child is still lesser than the value of the parent node. In short, nodes in the left subtree have lesser values than the parent node, and nodes in the right subtree have costs higher than the parent node.
Following is a visual representation of a sample Binary Search Tree:
Operations performed using Binary Search Trees
The programmers can quickly implement a binary search tree because it has an extremely organized structure and has lesser complexity. Moreover, the users can perform the following operations using BST:
- Searching
- Insertion
- Deletion
- Traversal
Binary Search Tree Implementation in C++
After building a BST, a search operation can be performed using a binary search algorithm. To construct a BST in C++ following structure can be used to define it.
// building a BST in C++
struct BstNode
{
int value;
BstNode* left;
BstNode* right;
// constructor
BstNode(int v)
{
Value = v;
left = NULL;
right = NULL;
}
};
The above mentioned is a sample node of BST. Following is the explanation of various operations performed using Binary Search Tree in C++:
Insertion in BST
Inserting into BST is a simple process in which the function compares every new node value with the root node. If there does not exist any root node, the inserted key itself becomes the root node. If there is already a root node present, the newly entered value is compared with the root and placed as the right or left child. It depends on the new node’s value, whether it is greater or smaller than the root. The insert function implementation of BST is as follows:
//BST Insertion code in c++
BstNode* Insert(BstNode* node, int v)
{
If(node == NULL)
{
node = new BstNode;
node->value = v;
node->left = NULL;
node->right = NULL;
}
else if (node->value < v)
{
node->right = Insert(node->right, v);
}
else
{
node->left = Insert(node->left, v);
}
return node;
}
Searching in the BST
Search in BST can be implemented used both recursive and iterative methods. The function takes the key in both of these methods, which it needs to find and compare it with the root node. If the key is smaller than the root node’s value, it moves to the left of the root node and makes it the root node for the next iteration. Similarly, if the key is greater than the node’s value, it moves to the right subtree and repeats the procedure until it reaches the leaf node, i.e., the tree’s end. Additionally, If the key is not greater or smaller than the root, which means that it is equal to the root’s value, the function returns true, which means that it has found the key in the tree.
Moreover, in implementing the function, users can also keep the nodes’ count or store the search path to determine the key’s exact position in the node. However, the straightforward implementation of the iteration approach of the searching function in C++ is the following:
// searching the value/node in the BST
bool Search(struct BstNode* node, int k) //iterative approach
{
while (node != NULL) {
if (k < node->value) //move to the left subtree
node = node->left;
else if (k > node->value) // move to the right subtree
node = node->right;
else {
return true; // key is found, return true
}
}
return false;
}
Deletion from BST
Using BST’s delete operation, the programmers can remove any specified value or node from the tree without disturbing the tree’s sorting. The deletion function works by finding the specified matching node in the tree to remove it later. After removing the desired node, it sorts the BST to avoid any dispositioning occurring in the tree. There are the following scenarios considered while removing from a BST:
- To be removed node is a leaf node
- To be removed node has one child only
- To be removed node has two children
//Deletion from BST in C++
BstNode* Delete(BstNode* node, int v)
{
BstNode* temp;
if (node == NULL)
return node;
if (v < node->value)
node->left = Delete(node->left, v);
else if (v > node->value)
node->right = Delete(node->right, v);
else if (node->left && node->right) {
Temp = Min(node->right);
node->value = temp->value;
node->right = Delete(node->right, node->value)
}
else {
temp = node;
if (node->right == NULL)
node = node->left;
else if (node->left == NULL)
node = node->right;
delete temp;
}
return node;
}
Here Min () is the function that finds the minimum node from the tree. This algorithm removes any desired node from the tree while maintaining the balance in it.
Traversal of the BST
Unlike linear data structures such as an array, list, queue, stack, which the users can traverse only in one way, the BST can be traversed in many ways. Mostly, the traversal pattern depends on the users’ needs and can differ from one another. The most commonly used traversal methods are:
- Breadth-first traversal: This type of traversal is also called level-order traversal. In this traversal method, the function traverses all nodes at the same level first and then moves to the next level. In doing so, it traverses bottom level nodes at the end. The breadth-first traversal of the above BST gives 50, 40, 60, 35, 45, 55, and 65.
- Depth-first traversal: The depth-first traversal methods are of three types:
- In-order traversal: This traversal method follows the pattern of the left, root, and then right. The function first moves to the tree’s left-most child node and traverses it, then its parent and then the right sibling. It traverses the values of BST in the ascending order, which is why it is the most used traversal method for BST. The above tree’s in-order traversal is 35, 40, 45, 50, 55, 60, and 65
- Pre-order traversal: This traversal method follows the same pattern as above with the slight change in order: the root, left, and then right. The above tree’s pre-order traversal is 5 0, 40, 35, 45, 60, 55, and 65.
- Post-order traversal: The traversal pattern of the post-order method is left, right, and then root. The above tree’s post-order traversal is 35, 45, 40, 55, 65, 60, and 50.
Below is the recursive implementation of in-order traversal in C++:
void inorder(BSTnode*& p)
{
if (p ! = NULL) {
if (p->left != NULL)
inorder(p->left); //traverses the left subtree
cout << " " << p->value << " "; //traverses the root value
if (p->right != NULL)
inorder(p->right); //traverses the right subtree
}
else
return;
}
Advantages of Using Binary Search Tree
The binary search tree elements are divided into two portions, making the search operation relatively easy. Suppose the value that the user wants to search is located somewhere in the tree. In that case, the algorithm discards the half side of the tree, where the possibility of finding those particular elements is negligible. In addition to this, BST has the following advantages:
Efficient Searching Algorithm
Searching becomes much faster when it comes to working with BST. It does not need to traverse the whole tree and go through every element to find the desired solution. BST takes log2(n) time complexity for a search in the worst-case scenario. In the above expression, n is the number of elements in the given sorted array.
Fast Operations
Insertion, deletion, searching, and updating operations are much faster in binary search trees than others because of their efficient way of storing values inside the nodes.
Easy Implementation
The coding of the binary search tree is relatively less complicated than other data structures in terms of implementation. The code is easily understandable, and debugging takes less time to find bugs in the implemented code.
Simple Traversal Technique
As the BST stores nodes’ values in a sorted way, it becomes easy to do in order and reverse order traversals when finding a value in the tree.
Order Statics
Ordered statistics are applicable in the BST. For example, we can perform queries like nth smallest or nth largest element and the ranged queries like finding values between node ‘a’ and node ‘b.’
Height of Binary Search Tree
Basic operations are relative to the height of a tree. If the user searches for a particular value, the number of operations the user has to do is halved on each step.
In the algorithm, this is called O(log n). The user starts with an input size of some sort, and over time that size gets smaller. A straight linear search denotes as O(n). As the input size grows, it takes more time to run operations. O(n) abstractly is a 45-degree line starting at starting point zero on a chart and moves right. The horizontal scale represents the input’s size, and the vertical range represents the time it takes to complete.
The constant time is O(1). It does not matter how significant or small the input size is. The operation takes place at the same time. For example, pop() and push() off of an array operate in continuous time.
The user has a recursive function, and our base case is: ‘if the user has no node, the user starts at this. Root’. It implies that the user can start at values, the user in the tree, and get tree sub-heights.
If the user passes it, the user recursively moves down the tree and adds the function calls to the performance stack (other articles). When the user gets to the bottom, the stack gets filled. The calls get executed as it compares the heights of the left and the right and increments by one.
Time Complexity
Searching
For searching element 1, the user has to navigate all elements (in order 3, 2, 1). Thus, searching in a binary search tree has a worst-case complexity of O(n). In general, the time complexity is O(h), where h is the height of BST.
Insertion
For inserting element 0, it must insert as the left child of 1. Therefore, the user needs to traverse all elements (in order 3, 2, 1) to insert 0, which has the worst-case complexity of O(n). In general, the time complexity is O(h).
Deletion
For deletion of element 1, the user have to traverse all elements to find 1 (in order 3, 2, 1). Therefore, deletion in a binary tree has the worst-case complexity of O(n). In general, the time complexity is O(h).
Disadvantages of Using Binary Search Tree
The disadvantage is that the user should consistently implement a balanced binary search tree – AVL tree, Red-Black tree, Splay tree. Otherwise, the cost of the operation may not be logarithmic and perverted into a linear search on an array.
- It employs a recursive approach, which requires more space in the stack adapter.
- Programming binary search algorithm is error-prone and arduous.
- The interface of binary search with memory hierarchy as caching is poor.
