Search

# Binary Search Tree (BST)

Updated: Jun 25

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;

1. All nodes of left subtree are less than the root node

2. All nodes of the right subtree are more than the root node

3. 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.

40 is to be deleted
Delete the node

Case II

In the second case, the node to be deleted has a single child node.

In such case:

1. Replace that node with its child node.

2. Remove the child node from its original position.

60 is to be deleted
Copy the value of its child to the node and delete the child
Final Tree

Case III

In this case, the node to be deleted has two children.

In such case:

1. Get the inorder successor of that node.

2. Replace the node with the inorder successor.

3. Remove the inorder successor from its original position.

30 is to be deleted

Copy the value of the inorder successor(40) to the node
Delete the inorder successor

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!