Binary Search Tree using C Programming

An important application of binary tree is their use in searching. Let us assume that each node in the tree is assigned a key value. In our examples, we will assume for simplicity that these are integers, although arbitrarily complex keys are allowed. We will also assume that all the keys are distinct, and deal with duplicates later.

The property that makes a binary tree into a binary search tree is that for every node, X, in the tree, the values of all the keys in the left subtree are smaller than the key value in X, and the values of all the keys in the right subtree are larger than the key value in X.

Notice that this implies that all the elements in the tree can be ordered in some consistent manner.

Insertion can be done in Binary Search Tree as follows:

Step 1:Strat from the root node.
Step 2:If the data to be inserted is x, compare it with the root value.
Step 2.1:If they are equal then just stop.
Step 2.2:If the data to be inserted is less than the root value then choose the left sub-tree.
Step 2.3If the data to be inserted is greater than the root value then choose the right sub-tree.
Step 3:Repeat step 2 until the value is properly positioned.

The above mechanism is clearly shown in the following Fig 1.

when we delete a node from Binary Search Tree then the deleted node may fall in either of the three cases.

Case 1:Deleted node has no child.
Case 2:Deleted node has exactly one child.
Case 3:Deleted node has Two children.

In case 1 we simply delete the node but in case 2 we replace the node with its child. In case 3 the deleted node is replaced by the in-order successor of the node. All three cases has been shown in the following Figure.

Source code

#include <stdio.h> #include <stdlib.h> typedef struct Node { int key; struct Node *left; struct Node *right; } node; node *newNode(int item) { node *temp = (node *)malloc(sizeof(node)); temp->key = item; temp->left = temp->right = NULL; return temp; } void inorder(node *root) { if (root != NULL) { inorder(root->left); printf("%d ", root->key); inorder(root->right); } } void preorder(node *root) { if (root != NULL) { printf("%d ", root->key); preorder(root->left); preorder(root->right); } } void postorder(node *root) { if (root != NULL) { postorder(root->left); postorder(root->right); printf("%d ", root->key); } } node* insert(node* nd, int key) { if (nd == NULL) return newNode(key); if (key < nd->key) nd->left = insert(nd->left, key); else nd->right = insert(nd->right, key); return nd; } node * minValueNode(node* nd) { node* current = nd; while (current->left != NULL) current = current->left; return current; } node* delete(node* root, int key) { if (root == NULL) { printf("The tree is empty!"); return root; } if (key < root->key) root->left = delete(root->left, key); else if (key > root->key) root->right = delete(root->right, key); else { if (root->left == NULL) { node *temp = root->right; free(root); return temp; } else if (root->right == NULL) { node *temp = root->left; free(root); return temp; } node* temp = minValueNode(root->right); root->key = temp->key; root->right = delete(root->right, temp->key); } return root; } int main() { node *root=NULL; int ch, value; while(1) { printf("\nChoices are as follows:"); printf("\n1:Insert a node"); printf("\n2:Traversal"); printf("\n3:Delete a node"); printf("\n4:Exit"); printf("\nEnter your choice:"); scanf("%d",&ch); switch(ch) { case 1: printf("\nEnter a value to insertion:"); scanf("%d",&value); root = insert(root,value); break; case 2: inorder(root); printf("\n"); preorder(root); printf("\n"); postorder(root); printf("\n"); break; case 3: printf("\nEnter a value for deletion:"); scanf("%d",&value); root = delete(root,value); break; case 4: return 0; } } return 0; }

---

Happy Exploring!