Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.

• It is called a binary tree because each tree node has a maximum of two children.
• It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time.

The properties that separate a binary search tree from a regular binary tree are :

• All nodes of left subtree are less than the root node
• All nodes of right subtree are more than the root node
• Both subtrees of each node are also BSTs i.e. they have the above two properties

Operations in Binary Search Tree:

Search :

The algorithm depends on the property of BST that if each left subtree has values below root and each right subtree has values above the root.

If the value is below the root, we can say for sure that the value is not in the right subtree; we need to only search in the left subtree and if the value is above the root, we can say for sure that the value is not in the left subtree; we need to only search in the right subtree.

                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)
            

Insert :

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

                if node == NULL 
                    return createNode(data)
                if (data < node->data)
                    node->left  = insert(node->left, data);
                else if (data > node->data)
                    node->right = insert(node->right, data);  
                return node;
            

Delete :

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 the leaf node. In such a case, simply delete the node from the tree.

Case II
In the second case, the node to be deleted lies has a single child node. In such a case follow the steps below:

1. Replace that node with its child node.
2. Remove the child node from its original position.

Case III
In the third case, the node to be deleted has two children. In such a case follow the steps below:

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.

Algorithm

1. Create a structure with an element (Element) and two pointers - Left and Right that points to the left and right child node respectively in the tree.
2. Create a new node using malloc function and assign the resultant pointer variable to the root node pointer T and assign it to NULL.
3. To insert a new element X into the tree:
   • If the value of T is NULL, assign T->Element to X, and the left and right child pointers to NULL and exit the insertion operation.
   • Otherwise if the element to be inserted is less than the root element T, repeat the step 3 recursively, with the new value of T as T->Left.
   • Otherwise if the element to be inserted is more than the root element T, repeat the step 3 recursively, with the new value of T as T->Right.
   • If the element is already present in the tree, do nothing.
4. To delete an element X from the tree:
   • Find the node where the element resides.
   • If the node has no left and right children, then the pointer to that node from the parent is changed to NULL and the node is freed of its memory.
   • If the node has only one child, then the parent of the node is made to point to the child of the node and the node is freed.
   • If the node has both left and right children:
     1. Look at the right subtree of the node (subtree rooted at the right child of the node).
     2. Find the Minimum there.
     3. Replace the key of the node to be deleted by the minimum element.
     4. Delete the minimum element.
5. To find an element X in the tree with root node T:
   • If the root node T is initially NULL, then the tree is empty. So return NULL and exit.
   • Take element X and compare it with the root node. If X is less than the element found at the root node, then repeat step 5 recursively with the new value of T as T->Left. Take element X and compare it with the root node. If X is more than the element found at the root node, then repeat step 5 recursively with the new value of T as T->Right.
6. To find the minimum element in a tree with root node T:
   • If T is NULL return NULL.
   • Otherwise slide the value of T to T->Left until T->Left becomes NULL.
   • Return the value of T.
7. To find the maximum element in a tree with root node T:
   • If T is NULL return NULL.
   • Otherwise, slide the value of T to T->Right until T->Right becomes NULL.
   • Return the value of T.

Program using C

//BINARY SEARCH TREE USING LINKED LIST #include <stdio.h> #include <stdlib.h> struct treeNode { int data; struct treeNode *left, *right; }; struct treeNode *root = NULL; //create bst node function struct treeNode* createNode(int data) { struct treeNode *newNode; newNode = (struct treeNode *) malloc(sizeof (struct treeNode)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return(newNode); } //function to insert into BST void insertion(struct treeNode **node, int data) { if (*node == NULL) { *node = createNode(data); } else if (data < (*node)->data) { insertion(&(*node)->left, data); } else if (data > (*node)->data) { insertion(&(*node)->right, data); } } //Function for inorder traversal left-root-right void intraverse(struct treeNode *node) { if (node != NULL) { intraverse(node->left); printf("%3d\t", node->data); intraverse(node->right); } return; } //Function for preorder traversal root-left-right void pretraverse(struct treeNode *node) { if (node != NULL) { printf("%3d\t", node->data); pretraverse(node->left); pretraverse(node->right); } return; } //Function for postorder traversal left-right-root void posttraverse(struct treeNode *node) { if (node != NULL) { posttraverse(node->left); posttraverse(node->right); printf("%3d\t", node->data); } return; } int main() { int data, ch; while (1) { printf("BINARY SEARCH TREE \nMENU\n============\n"); printf("1. Insertion in Binary Search Tree\n"); printf("2. Inorder traversal\n"); printf("3. Preorder traversal\n"); printf("4. Postorder traversal\n5. Exit\n"); printf("Enter your choice:"); scanf("%d", &ch); switch (ch) { case 1: while (1) { printf("Enter your data:"); scanf("%d", &data); insertion(&root, data); printf("Do U want more Insertion?(enter 0 for no/1 for yes ):"); scanf("%d", &ch); if (!ch) break; } break; case 2: printf("Inorder Traversal:\n"); intraverse(root); printf("\n"); break; case 3: printf("Preorder Traversal:\n"); pretraverse(root); printf("\n"); break; case 4: printf("Postorder Traversal:\n"); posttraverse(root); printf("\n"); break; case 5: exit(0); default: printf("u've entered wrong option\n"); break; } } return 0; }