.png)
It is a data structure that quickly allows us to maintain a sorted list of numbers.
Also:
It is called a binary tree because each tree node has max two children
It is called search tree because it can be used to search for the presence of number in O(log(n)) time
Now you might wonder what differentiates it from the regular binary tree;
All nodes of left subtree are less than the root node
All nodes of the right subtree are more than the root node
Both subtrees of each node are also BST's which means they follow the above two properties.
There are three basic operations that you can perform on a binary search tree:
1. Search Operation
The algorithm depends on the property of BST that if each left subtree has values less than root and each right subtree has values greater than root.
If the value is less than root we can say for sure that the value is not in the right subtree; now we need to only search in the left subtree and
If the value is less than root we can say for sure that the value is not in the left subtree; now we need to only search in the right subtree.
Algorithm:
if root == NULL
return NULL;
if number == root -> data
return root -> data;
if number < root -> data
return search( root->left );
if number > root -> data
return search( root -> right ); 2. Insertion Operation
A new key is always inserted at the leaf. Inserting a value in the correct position is similar to searching because we try to maintain the rule that the left subtree is lesser than root and right subtree is larger than root.
We keep going to either right subtree or left subtree depending on the value and when we reach a point left or right subtree is null, we put the new node there.
Algorithm:
if node == NULL
return create_Node(data);
if (data < node -> data)
node ->left = insert(node ->left, data);
else if (data > node ->data)
node ->right = insert(node ->right, data);
return node;3. Deletion Operation
There are three cases for deleting a node from a binary search tree.
Case I
In the first case, the node to be deleted is a leaf node so simply delete the node from the tree.
Case II
In the second case, the node to be deleted has a single child node.
In such case:
Replace that node with its child node.
Remove the child node from its original position.
Case III
In this case, the node to be deleted has two children.
In such case:
Get the inorder successor of that node.
Replace the node with the inorder successor.
Remove the inorder successor from its original position.
Implementation using C:
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left, *right;
};
// Create a node
struct node *newNode(int item) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// Inorder Traversal
void inorder(struct node *root) {
if (root != NULL) {
// Traverse left
inorder(root->left);
// Traverse root
printf("%d -> ", root->key);
// Traverse right
inorder(root->right);
}
}
// Insert a node
struct node *insert(struct node *node, int key) {
// Return a new node if the tree is empty
if (node == NULL) return newNode(key);
// Traverse to the right place and insert the node
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
// Find the inorder successor
struct node *minValueNode(struct node *node) {
struct node *current = node;
// Find the leftmost leaf
while (current && current->left != NULL)
current = current->left;
return current;
}
// Deleting a node
struct node *deleteNode(struct node *root, int key) {
// Return if the tree is empty
if (root == NULL) return root;
// Find the node to be deleted
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// If the node is with only one child or no child
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;
}
// If the node has two children
struct node *temp = minValueNode(root->right);
// Place the inorder successor in position of the node to be deleted
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
// Driver code
int main() {
struct node *root = NULL;
root = insert(root, 80);
root = insert(root, 30);
root = insert(root, 10);
root = insert(root, 60);
root = insert(root, 70);
root = insert(root, 100);
root = insert(root, 140);
root = insert(root, 40);
printf("Inorder traversal: ");
inorder(root);
printf("\nAfter deleting 10\n");
root = deleteNode(root, 10);
printf("Inorder traversal: ");
inorder(root);
}Output:
Inorder traversal: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 14 ->
After deleting 10
Inorder traversal: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 14 -> Happy Coding!
Follow us on Instagram @programmersdoor
Join us on Telegram @programmersdoor
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.
Follow Programmers Door for more.