Learn DSA & Get Ready for MAANG Companies Start Now!!
As we discussed in the previous article, the binary search tree is one of the types of trees with some specific properties. A binary search tree is quick, efficient, and easy to implement. In this article, we will learn the working of a binary search tree, its properties, and its implementation.
Binary search tree
BST, short for Binary search tree is a binary tree with specific following properties.
1. The nodes in the left subtree must be less than the root node
2. The nodes in the right subtree must be greater than the root node.
3. The left and the right subtrees must also be binary trees.
The above properties apply to each node of the binary tree for it to be a BST.
Operations on Binary Search Tree in data Structure
1. Searching in BST
Finding the location of an element in the BST
Algorithm
search(root)
If root == NULL
return NULL;
If Value == root->data
return root->data;
If Value < root->data
return search(root->left)
If Value > root->data
return search(root->right)
2. Inserting element in BST
Inserting a new element in the BST
Algorithm
createNode(newvalue)
If node == NULL
return createNode(newvalue)
if (newvalue < node->data)
node->left = insert(node->left, newvalue);
else if (newvalue > node->data)
node->right = insert(node->right, newvalue);
return node;
3. Deleting element from BST
deleting an existing element from BST
Case 1: if a node is to be deleted from the Leaf node.
- Simply Delete the node from the leaf node.
Case 2: if the node that has to be deleted has 1 child
- Replace node with the child node
- Remove child node from the original position
Case 3: if the node that has to be deleted has 2 child
- Retrieve inorder successor of the node.
- Replace node with the inorder successor
- Remove inorder successor from its original position.
Working of Binary Search Tree
Let us take an example to demonstrate the working of BST with insert and delete operations
Step 1: insert 50
Step 2: insert 75
Step 3: insert 90
Step 4: insert 25
Step 5: insert 40
Step 6: insert 62
Step 7: insert 70
Step 8: delete 90. This is case 1 deletion.
Step 9: insert 92
Step 10: delete 25. This is case 2 deletion.
Step 11: delete 75. This is case 3 deletion.
Step 12: insert 30
Implementation of Binary Search Tree in C
#include <stdio.h>
#include <stdlib.h>
struct node
{
int key;
struct node *left, *right;
};
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorderTraversal(struct node *root)
{
if (root != NULL)
{
inorderTraversal(root->left);
printf("%d -> ", root->key);
inorderTraversal(root->right);
}
}
struct node *insertNew(struct node *node, int Value)
{
if (node == NULL) return newNode(Value);
if (Value< node->key)
node->left = insertNew(node->left, Value);
else
node->right = insertNew(node->right, Value);
return node;
}
struct node *minValueNode(struct node *node)
{
struct node *current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
struct node *deleteNode(struct node *root, int Value)
{
if (root == NULL) return root;
if (Value < root->key)
root->left = deleteNode(root->left, Value);
else if (Value > root->key)
root->right = deleteNode(root->right, Value);
else
{
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct node *temp = root->left;
free(root);
return temp;
}
struct node *temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
int main() {
struct node *root = NULL;
root = insertNew(root, 8);
root = insertNew(root, 3);
root = insertNew(root, 1);
root = insertNew(root, 6);
root = insertNew(root, 7);
root = insertNew(root, 10);
root = insertNew(root, 14);
root = insertNew(root, 4);
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\nAfter deleting 10\n");
root = deleteNode(root, 10);
printf("Inorder traversal: ");
inorderTraversal(root);
}
Binary Search Tree Implementation in C++
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
struct node
{
int key;
struct node *left, *right;
};
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorderTraversal(struct node *root)
{
if (root != NULL)
{
inorderTraversal(root->left);
printf("%d -> ", root->key);
inorderTraversal(root->right);
}
}
struct node *insertNew(struct node *node, int Value)
{
if (node == NULL) return newNode(Value);
if (Value< node->key)
node->left = insertNew(node->left, Value);
else
node->right = insertNew(node->right, Value);
return node;
}
struct node *minValueNode(struct node *node)
{
struct node *current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
struct node *deleteNode(struct node *root, int Value)
{
if (root == NULL) return root;
if (Value < root->key)
root->left = deleteNode(root->left, Value);
else if (Value > root->key)
root->right = deleteNode(root->right, Value);
else
{
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct node *temp = root->left;
free(root);
return temp;
}
struct node *temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
int main() {
struct node *root = NULL;
root = insertNew(root, 8);
root = insertNew(root, 3);
root = insertNew(root, 1);
root = insertNew(root, 6);
root = insertNew(root, 7);
root = insertNew(root, 10);
root = insertNew(root, 14);
root = insertNew(root, 4);
cout << "Inorder traversal: ";
inorderTraversal(root);
cout << "\nAfter deleting 10\n";
root = deleteNode(root, 10);
cout << "Inorder traversal: ";
inorderTraversal(root);
}
BST Implementation in JAVA
public class BinarySearchTree
{
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
Node root;
BinarySearchTree()
{
root = null;
}
void insert(int key)
{
root = insertKey(root, key);
}
Node insertKey(Node root, int key)
{
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key)
root.left = insertKey(root.left, key);
else if (key > root.key)
root.right = insertKey(root.right, key);
return root;
}
void inorder()
{
inorderRec(root);
}
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left);
System.out.print(root.key + " -> ");
inorderRec(root.right);
}
}
void deleteKey(int key)
{
root = deleteRec(root, key);
}
Node deleteRec(Node root, int key)
{
if (root == null)
return root;
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
else
{
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.key = minValue(root.right);
root.right = deleteRec(root.right, root.key);
}
return root;
}
int minValue(Node root)
{
int minv = root.key;
while (root.left != null)
{
minv = root.left.key;
root = root.left;
}
return minv;
}
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
tree.insert(8);
tree.insert(3);
tree.insert(1);
tree.insert(6);
tree.insert(7);
tree.insert(10);
tree.insert(14);
tree.insert(4);
System.out.print("Inorder traversal: ");
tree.inorder();
System.out.println("\n\nAfter deleting 10");
tree.deleteKey(10);
System.out.print("Inorder traversal: ");
tree.inorder();
}
}
Binary Search Tree Implementation in Python
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def inorderTraversal(root):
if root is not None:
inorderTraversal(root.left)
print(str(root.key) + "->", end=' ')
inorderTraversal(root.right)
def insertnew(node, value):
if node is None:
return Node(value)
if value< node.key:
node.left = insertnew(node.left, value)
else:
node.right = insertnew(node.right, value)
return node
def minValueNode(node):
current = node
while(current.left is not None):
current = current.left
return current
def deleteNode(root, value):
if root is None:
return root
if value < root.key:
root.left = deleteNode(root.left, value)
elif(value> root.key):
root.right = deleteNode(root.right, value)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = minValueNode(root.right)
root.key = temp.key
root.right = deleteNode(root.right, temp.key)
return root
root = None
root = insertnew(root, 8)
root = insertnew(root, 3)
root = insertnew(root, 1)
root = insertnew(root, 6)
root = insertnew(root, 7)
root = insertnew(root, 10)
root = insertnew(root, 14)
root = insertnew(root, 4)
print("Inorder traversal: ", end=' ')
inorderTraversal(root)
print("\nDelete 10")
root = deleteNode(root, 10)
print("Inorder traversal: ", end=' ')
inorderTraversal(root)
Advantages of Binary Search Tree
1. Searching is very easy in BST. At each step, we get to know which subtree might contain the element.
2. Insertion and deletion in BST is faster than arrays or linked lists
3. BST is very efficient in terms of complexity.
Complexity of Binary Search Tree
Space complexity for all operations in BST in O(n)
| Operation | Best case | Average case | Worst Case |
| Searching | O(log n) | O(log n) | O(n) |
| Insertion | O(log n) | O(log n) | O(n) |
| deletion | O(log n) | O(log n) | O(n) |
Applications of BST
1. It is implemented for dynamic sorting
2. It manages virtual memory area in UNIX kernel
3. It’s useful for multilevel indexing in database
Conclusion
BST is a fast and efficient algorithm with many real-world applications and advantages. We learned working and implementation of BST in different programming languages. In future articles, we will learn about AVL trees and, B-Tree, etc.