Binary Search Tree (BST) | Data Structures Using C Tutorials

In this page

In this tutorial, you will learn what is a binary search tree, how different operations like insertion, deletion, searching are done in a binary search tree with examples in C and what are the applications of binary search trees.

A Binary Search Tree is a special binary tree used for the efficient storage of data. The nodes in a binary search tree are arranged in order. It also allows for the simple insertion and deletion of items.

It is a binary tree where each node can have a maximum of two childern.
It is called a search tree, since it can search for and find an element with an avergae running time f(n) = O(log₂n)

A binary search tree has the following properties:

All the elements in the left subtree is less than the root node.
All the elements in the right subtree is greater than the root node.
These properties are shared by both the left and right trees i.e. they are also BSTs.

An example for a binary search tree is given below:

Operations on a Binary Search Tree

A binary search tree can perform three basic operations: searching, insertion, and deletion.

Searching in a Binary Search Tree

The search operation finds whether or not a particular value exists in a tree. Since the binary search tree is ordered, the search can be easily made.

Suppose we want to find X in a binary tree having root R.

Compare item, X, with the root, R, of the tree.
- If X < R, then recursively search on the left subtree of the tree.
- If X > R, then recursively search on the right subtree of the tree.

Repeat these steps until we reach an empty subtree or locate a node R such that R = X. That is, we continue the search from the root down the tree until we reach X or a terminal node.

Algorithm: Search

‎IF ROOT = NULL
‎   Return NULL
‎ELSE
‎   IF ROOT -> DATA = X
‎      Return ROOT
‎   ELSE
‎      IF X < ROOT -> DATA
‎         Return Search(ROOT -> LEFT, X)
‎      ELSE
‎         Return Search(ROOT -> RIGHT, X)
‎      [END OF IF]
‎   [END OF IF]
‎[END OF IF]

Consider the following BST and suppose we want to find 43. Start from root node 50.

Move to the left subtree of root since 43<50.

Now compare 43 and 41. Since 43>41move to the right subtree.

Now 43<47, So move to the right subtree, where 43 is found.

Inserting in a Binary Search Tree

The insert operation is similar to the search operation. This is because first, you have to find the correct position where the new element is to be inserted.

If the tree is NULL, insert new element as the root.
Otherwise, depending on the value, we continue to the right or left subtree, and when we reach a position where the left or right subtree is null, we insert the new node there.

Algorithm: Insert

IF TREE = NULL
‎   Allocate memory for TREE
‎   SET TREE -> DATA = VAL
‎   SET TREE -> LEFT = TREE -> RIGHT = NULL
ELSE
‎   IF VAL < TREE -> DATA
‎      Insert(TREE LEFT, VAL)
‎   ELSE
‎      Insert(TREE RIGHT, VAL)
‎   [END OF IF]
[END OF IF]

Consider the following BST and suppose we want to insert a new node 42.

Start searching for element 42 from the root. The search will stop when we reach node 43.

Since 43>42 but 43 has no left subtree. So we insert 43 as the left child of node 43.

Deleting from a Binary Search Tree

The deletion operation is to be done very carefully that the properties of the binary search tree are not violated and no nodes are lost.

Deletion is done in the following three cases:

Deleting a node that has no children.
Deleting a node with one child.
Deleting a node with two children.

Case 1: Deleting a node that has no children

Here the node we have to delete is a leaf node. So, we can simply delete the node from the tree.

Suppose we want to delete node 58 from the following tree.

Simply delete node 58.

Case 2: Deleting a node with one child.

The following steps are to be done to delete a node that has only a single child.

Replace the node with its child.
Remove the child node.

Suppose we want to delete node 47 from the following tree.

Replace node 47 with its child node 43.

Now delete the child node 43 from its original position

Case 3: Deleting a node with two children

The case is when the node we want to delete has 2 children. This case can be handled by the following steps:

Replace the node’s value with it’s in-order successor.
Remove the in-order successor from its original position.

Suppose we want to delete node 41 from the following tree.

Replace the value of node 41 with its in-order successor 43.

Now delete node 43 from its original position.

Algorithm: Deletion

IF TREE = NULL
‎   Write "VAL not found in the tree"
ELSE IF VAL < TREE->DATA
‎   Delete(TREE->LEFT, VAL)
ELSE IF VAL > TREE->DATA
‎   Delete(TREE->RIGHT, VAL)
ELSE IF TREE->LEFT AND TREE->RIGHT
‎   SET TEMP = findLargestNode(TREE->LEFT)
‎   SET TREE->DATA = TEMP->DATA
‎   Delete(TREE->LEFT, TEMP->DATA)
ELSE
‎   SET TEMP = TREE
‎   IF TREE->LEFT = NULL AND TREE->RIGHT = NULL
‎      SET TREE = NULL
‎   ELSE IF TREE LEFT != NULL
‎      SET TREE = TREE LEFT
‎   ELSE
‎      SET TREE = TREE RIGHT
‎   [END OF IF]
‎   FREE TEMP
[END OF IF]

Applications of Binary Search Tree

Used for indexing and multilevel indexing in the database.
Used to implement various searching algorithms.
For dynamic sorting.
Used for managing virtual memory areas in unix kernal.