Binary Search Tree Program in C

Introduction to Binary Search Tree in C

A binary search tree is a tree data structure that allows the user to store elements in a sorted manner. It is called a binary tree because each node can have a maximum of two children and is called a search tree because we can search for a number in $O(log(n))$ time.

The properties of a regular binary tree are:

1. All nodes in the left subtree have a value less than the root node
2. All nodes in the right subtree have a value more than the root node
3. Both subtrees of each node are also binary search trees, i.e. they have the above two properties

Example of Binary Search Tree in C

The diagram below demonstrates two binary search trees, one follows all the properties of a binary search tree, while the other violates the rule.

The binary tree on the right isn't a binary search tree because the right subtree of node 3 contains a value smaller than it.

Operations to Perform on Binary Search Tree in C

Three basic operations can be performed on a binary search tree :

Search Operation

In Search, we have to find a specific element in the data structure. This searching operation becomes simpler in binary search trees because here elements are stored in sorted order.

Algorithm for searching an element in a binary tree is as follows:

1. Compare the element to be searched with the root node of the tree.
2. If the value of the element to be searched is equal to the value of the root node, return the root node.
3. If the value does not match, check whether the value is less than the root element or not if it is then traverse the left subtree.
4. If larger than the root element, traverse the right subtree.
5. If the element is not found in the whole tree, return NULL.

Let us now understand search operation in a binary search tree program in c with the help of an example where we are trying to search for an item having a value of 20:

Step 1:

Step 2:

Step 3:

Insert Operation

Inserting an element in a binary search tree is always done at the leaf node. To perform insertion in a binary search tree, we start our search operation from the root node, if the element to be inserted is less than the root value or the root node, then we search for an empty location in the left subtree, else, we search for the empty location in the right subtree.

Algorithm for inserting an element in a binary tree is as follows:

Let us now understand insertion operation in a binary search tree with the help of an example where we are trying to insert an item having a value of 65:

Deletion Operation

In the deletion operation, we have to delete a node from the binary search tree in a way that does not violate its properties. Deletion can occur in three possible cases:

1. Node to be deleted is the leaf node

This is the simplest case of deleting a node in a binary search tree. Here, we will replace the leaf node with NULL and free the allocated space.

We can understand the deletion operation in a binary search tree with the help of an example where we are trying to delete the node having a value of 90

2. Node to be deleted has a single child node

In this case, we will replace the target node with its child and then delete that replaced child node. This means that the child node will now contain the value to be deleted. So, we will just replace the child node with NULL and free up the allocated space.

In the below example, we have to delete a node having a value of 79, and this node to be deleted has only one child, so it will be replaced with its child 55.

3. The node to be deleted has two children

This case is complex as compared to the previous two. Here we follow certain steps to delete the node:

• We will find the inorder successor of the target node, which has to be deleted
• Now, replace this node with the successor until the target node is at the leaf
• Replace the target node with NULL and free up the allocated space

In the below example, we have to delete node 45, which is the root node, so first, it will be replaced with its in-order successor, which is 55. Now, node 45 will be at the leaf of the tree so that it can be deleted easily.

Program to Implement Binary Search Tree in C

Let us now implement the creation of a node and traversals in Binary Trees using C programming. Here, we will focus on the operations related to the binary search tree like inserting a node, deleting a node, searching, etc.

Example

Output

Explanation

The search function checks if(root==NULL || root->data==x) which means if the root is NULL then the element is not in the tree and if the root is equal to the target value x then the element is found. Otherwise, we implement else if(x > root->data), i.e. if the target element is greater than the root node data, we will search in the right subtree using search(root->right_child, x).Else, in the left subtree using search(root->left_child, x).

In the insert function, if we have to insert a new node to the right child of a node X, we will first create a new node that is returned by insert(root->right_child, x) and then make the right child of X equal to that root->right_child = insert(root->right_child, x). Thus, after searching if we reach a null node, then we just insert a new node there using if(root==NULL) → return new_node(x).

In the delete function, if the node to be deleted has no children we do if(root->left_child==NULL && root->right_child==NULL) which will simply delete the node and free up the allocated space.

While, if the node has only one child, we check if(root->left_child==NULL) which means that only the right child exists and we have to delete this node and have to point its parent to its child, so we are storing its child into a temporary variable using temp = root->right_child and then deleting the node.

If the node has two children, we find the minimum element of the right subtree using find_minimum(root->right_child). Now, we replace the data of the node to be deleted with the data of this node using root->data = temp->data. And then delete the node found by the minimum function using delete(root->right_child, temp->data).

Binary Search Tree Program in C: Array Representation and Traversals

Now we will be implementing a binary search tree program in C using an array. We will use array representation to make a binary tree in C and then implement inorder, preorder, and postorder traversals.

Let us consider the array given below and try to draw a tree from it:

In the above image \0 represents NULL, like for node B both the right child and left child are NULL which implies B is a leaf node.

Example

Output

Explanation

The above-created binary tree can be represented as an array below:

We check if the current node is not null, by tree[index]!='\0' along with (2*index)+1)<=max_node, to get the right child of node i is given by (2*i)+1 but this value must lie within the number of elements in the array. We return (2*index)+1 if both the above conditions are satisfied then we are returning the index of the right child and return -1 in case of failure, we are returning -1, a negative value to represent failure.

Similarly, we implemented a function to get the left child of the tree by using the property that the left child of node i of a complete binary tree is given by 2*i. So we made functions to traverse the binary tree.

Now, since we are done with our node structure and function to add new nodes. Our last task is to make the tree described in the above diagram and implement inorder, postorder, and preorder traversals to it.

The line if(index>0 && tree[index]!='\0') checks if the given index is valid or not because the functions we made above to get the children of the tree return -1 for an invalid result so, the condition index>0 checks the same. The condition tree[index]!='\0' checks if the node is not NULL or not.

Program for Binary Search Tree in C: Linked List Representation and Traversals

Now we will be implementing a binary tree in C using a linked list. We will use linked list representation to make a binary tree in C and then implement inorder, preorder, and postorder traversals.

Example

Output

Explanation

We create a node structure in C using,

• char data – data value which we will store in this node is of the type character.
• struct node *right_child – we will use this to link the current node with its right child.
• struct node *left_child – we will use this to link the current node with its left child.

After creating a node structure, we write a function to create new nodes of the tree. The following lines of code demonstrate the creation of a new node:

• struct node *temp – *temp is a node and ‘temp’ is a pointer to this node, which means that temp will store the address of the node. Our next task is to allocate the memory to the node and we will do it using the malloc function.
• temp = malloc(sizeof(struct node))– Now we allocate a space in the memory to the node and store the address of the memory in the variable temp.
  • temp->data = data – This line is used for storing data in our temp node.
  • p->left_child = NULL – Making the left child of the node null.
  • p->right_child = NULL – Similarly, we make the right child null.
  • return(temp) - Now we can simply return the address of the created node.

Now, since we are done with our node structure and function to add new nodes. Our last task is to make the tree described in the above diagram and implement inorder, postorder, and preorder traversals to it.

Complexity of Binary Search Tree in C

Time Complexity

Space Complexity

Here, n is the number of nodes in the tree.

Applications of Binary Search Tree in C

1. Binary search tree is used to implement multilevel indexing in databases.
2. We can use a binary search tree for dynamic sorting.
3. A binary search tree is used to manage virtual memory areas in the Unix kernel.