Binary Search Tree ADT

Binary Search Tree ADT

A binary search tree is a binary tree in which the nodes are arranged in a specific order. That means the values at the left subtree are less than the root node value. Similarly, the values at the right subtree are greater than the root node value. The binary search tree is based on the binary search algorithm.

In a binary search tree structure, the top root node holds a benchmark value. All values present in its left subtree strictly fall below the value of the root node, whereas all values in its right subtree strictly exceed the value of the root node. In the representation above, the root node value is $10$. The left subtree consists of node $7$, which has a left child $5$ and a right child $9$. The right subtree consists of node $15$, which has a left child $12$ and a right child $18$.

Operations on Binary Search Tree

Insertion of a Node in a Binary Search Tree

The step-by-step algorithm to insert a node into a binary search tree is defined as follows:

1. Read the value for the node which is to be created and store it in a node called New.

2. Initially, if (root != NULL), then root = New.

3. Again read the next value of node created in New.

4. If (New->value < root->value), then attach New node as a left child of root; otherwise, attach New node as a right child of root.

5. Repeat steps 3 and 4 for constructing the required binary search tree completely.

While inserting any node in a binary search tree, first look for its appropriate position in the binary search tree. Start comparing this new node with each node of the tree. If the value of the node which is to be inserted is greater than the value of the current node, move onto the right subbranch; otherwise, move onto the left subbranch. As soon as the appropriate position is found, attach this new node as a left or right child appropriately.

Consider inserting the value $23$ into the tree shown in the diagram above:

Start by comparing $23$ with the value of the root node, which is $10$. As $23$ is greater than $10$, move to the right subtree root, which is $20$. Next, compare $23$ with $20$ and move right to node $22$. Compare $23$ with $22$ and move right to node $24$. Now compare $23$ with $24$. Since $23$ is less than $24$, move to the left branch of $24$. As there is a NULL node as the left child of $24$, attach $23$ as the left child of 24$.\n\n\n\n## Deletion of an Element from the Binary Search Tree\n\nFor the deletion of any node from a binary search tree, three distinct cases are possible:\n\ni. Deletion of a leaf node.\n\nii. Deletion of a node having one child.\n\niii. Deletion of a node having two children.\n\nCase i: Deletion of a leaf node\n\nThis is the simplest deletion scenario, in which the left or right pointer of the parent node is set to `NULL`. For instance, to delete the node having value 6$from a tree where node$8$is its parent, set the left pointer of node$8 to `NULL`.\n\nCase ii: Deletion of a node having one child\n\nConsider a tree where node 15$has a single child node$18$(which in turn has a left child$16$). To delete node$15$, simply copy node$18$at the place of$15 and then set the node free. The inorder successor is always copied at the position of a node being deleted.\n\n\n\nCase iii: Deletion of a node having two children\n\nConsider deleting node 7$from a tree where node$7$has a left child$6$and a right child$9$(which has a left child$8):\n\nFind the inorder successor of node 7$, which is node$8$. Copy$8$at the position where the value of the node is$7$. Set the left pointer of node$9 as `NULL`. This completes the deletion procedure.\n\n\n\n## Searching a Node from Binary Search Tree\n\nIn searching, the node which is to be searched is called a key node. The key node is compared with each node starting from the root node. If the value of the key node is greater than the current node, search for it on the right subbranch; otherwise, search on the left subbranch. If a leaf node is reached and the value of the key node is still not found, declare "node is not present in the tree".\n\n\n\nTo search for value 9 in the binary search tree above:\n\nCompare 9$with the root node$10$. As$9$is less than$10$, search on the left subbranch (node$5$). Next, compare$9$with$5$. As$9$is greater than$5$, move to the right subbranch (node$8$). Compare$9$with$8$. As$9$is greater than$8$, move to the right subbranch. Read the node value as$9. Thus, the desired node is successfully located.\n\n# Program Implementation of Binary Search Tree\n\nThe complete C program implementation for performing insertion, deletion, searching, and displaying a Binary Search Tree in inorder fashion is given below:\n\n```c\n#include \n#include \n#include \n\ntypedef struct bst\n{\n int data;\n struct bst *left, *right;\n} node;\n\nvoid insert(node *, node *);\nvoid inorder(node *);\nnode *search(node *, int, node **);\nvoid del(node *, int);\nnode *get_node();\n\nvoid main()\n{\n int choice;\n char ans = 'N';\n int key;\n node *New, *root, *tmp, *parent;\n root = NULL;\n clrscr();\n\n printf("\n\t Program For Binary Search Tree ");\n do\n {\n printf("\n1.Create\n2.Search\n3.Delete\n4.Display");\n printf("\n\n Enter your choice :");\n scanf("%d", &choice);\n switch(choice)\n {\n case 1:\n do\n {\n New = get_node();\n printf("\n Enter The Element ");\n scanf("%d", &New->data);\n if(root == NULL) /* Tree is not Created */\n root = New;\n else\n insert(root, New);\n printf("\n Do u Want To enter More Elements?(y/n)");\n ans = getch();\n } while(ans == 'y');\n break;\n\n case 2:\n printf("\n Enter The Element Which You Want To Search");\n scanf("%d", &key);\n tmp = search(root, key, &parent);\n printf("\n Parent of node %d is %d", tmp->data, parent->data);\n break;\n\n case 3:\n printf("\n Enter The Element U wish to Delete");\n scanf("%d", &key);\n del(root, key);\n break;\n\n case 4:\n if(root == NULL)\n printf("Tree Is Not Created");\n else\n {\n printf("\n The Tree is: ");\n inorder(root);\n }\n break;\n }\n } while(choice != 5);\n}\n\nnode *get_node()\n{\n node *temp;\n temp = (node *)malloc(sizeof(node));\n temp->left = NULL;\n temp->right = NULL;\n return temp;\n}\n\n/* This function is for creating a binary search tree */\nvoid insert(node *root, node *New)\n{\n if(New->data < root->data)\n {\n if(root->left == NULL)\n root->left = New;\n else\n insert(root->left, New);\n }\n if(New->data > root->data)\n {\n if(root->right == NULL)\n root->right = New;\n else\n insert(root->right, New);\n }\n}\n\n/* This function is for searching the node from binary Search Tree */\nnode *search(node *root, int key, node **parent)\n{\n node *temp;\n temp = root;\n while(temp != NULL)\n {\n if(temp->data == key)\n {\n printf("\n The %d Element is Present", temp->data);\n return temp;\n }\n *parent = temp;\n if(temp->data > key)\n temp = temp->left;\n else\n temp = temp->right;\n }\n return NULL;\n}\n\n/* This function is for deleting a node from binary search tree. */\nvoid del(node *root, int key)\n{\n node *temp, *parent, *temp_succ;\n temp = search(root, key, &parent);\n\n /* deleting a node with two children */\n if(temp->left != NULL && temp->right != NULL)\n {\n parent = temp;\n temp_succ = temp->right;\n while(temp_succ->left != NULL)\n {\n parent = temp_succ;\n temp_succ = temp_succ->left;\n }\n temp->data = temp_succ->data;\n if(temp_succ == parent->left)\n parent->left = NULL;\n else\n parent->right = NULL;\n printf(" Now Deleted it!");\n return;\n }\n\n /* deleting a node having only one child */\n /* The node to be deleted has left child */\n if(temp->left != NULL && temp->right == NULL)\n {\n if(parent->left == temp)\n parent->left = temp->left;\n else\n parent->right = temp->left;\n temp = NULL;\n free(temp);\n printf(" Now Deleted it!");\n return;\n }\n\n /* The node to be deleted has right child */\n if(temp->left == NULL && temp->right != NULL)\n {\n if(parent->left == temp)\n parent->left = temp->right;\n else\n parent->right = temp->right;\n temp = NULL;\n free(temp);\n printf(" Now Deleted it!");\n return;\n }\n\n /* deleting a node which is having no child */\n if(temp->left == NULL && temp->right == NULL)\n {\n if(parent->left == temp)\n parent->left = NULL;\n else\n parent->right = NULL;\n printf(" Now Deleted it!");\n return;\n }\n}\n\n/* This function displays the tree in inorder fashion */\nvoid inorder(node *temp)\n{\n if(temp != NULL)\n {\n inorder(temp->left);\n printf("%d ", temp->data);\n inorder(temp->right);\n }\n}\n```\n\n# Execution Output and Examples\n\n## Program Execution Trace\n\nThe following trace details the creation, display, and searching steps during execution:\n\nChoice 1 (Create):\n- Enter The Element 10\n- Enter The Element 8\n- Enter The Element 9\n- Enter The Element 7\n- Enter The Element 15\n- Enter The Element 13\n- Enter The Element 14\n- Enter The Element 12\n- Enter The Element 16\n\nChoice 4 (Display):\n- Output: `The Tree is: 7 8 9 10 12 13 14 15 16`\n\nChoice 2 (Search):\n- Enter The Element Which You Want To Search: 16\n- Output: `The 16 Element is Present`, `Parent of node 16 is 15`\n\n## Exercise 4.9.1\n\nProblem Definition: Define binary search tree. Draw the binary search tree for the following sequence:\n14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5\n\nSolution Outline:\n\nA binary search tree is a binary tree in which all nodes are arranged such that left child values are strictly smaller than parent values, and right child values are strictly larger than parent values.\n\nConstruction sequence:\n- Step 1: Insert 14 (Root)\n- Step 2: Insert 15$(Right child of$14)\n- Step 3: Insert 4$(Left child of$14)\n- Step 4: Insert 9$(Right child of$4)\n- Step 5: Insert 7$(Left child of$9)\n- Step 6: Insert 18$(Right child of$15)\n- Step 7: Insert 3$(Left child of$4)\n- Step 8: Insert 5$(Left child of$7)\n- Step 9: Insert 16$(Left child of$18)\n- Step 10: Insert 4 (Duplicate value)\n- Step 11: Insert 20$(Right child of$18)\n- Step 12: Insert 17$(Left child of$20)\n- Step 13: Insert 9 (Duplicate value)\n- Step 14: Insert 14 (Duplicate value)\n- Step 15: Insert 5$$ (Duplicate value)