Explain Binary Search Tree?

Binary Search Tree

1. Binary Search tree can be defined as a class of binary trees, in which the nodes are arranged in a specific order. This is also called ordered binary tree.
2. In a binary search tree, the value of all the nodes in the left sub-tree is less than the value of the root.
3. Similarly, value of all the nodes in the right sub-tree is greater than or equal to the value of the root.
4. This rule will be recursively applied to all the left and right sub-trees of the root.

 

A Binary search tree is shown in the above figure. As the constraint applied on the BST, we can see that the root node 30 doesn't contain any value greater than or equal to 30 in its left sub-tree and it also doesn't contain any value less than 30 in its right sub-tree.

Advantages of using binary search tree

1. Searching become very efficient in a binary search tree since, we get a hint at each step, about which sub-tree contains the desired element.
2. The binary search tree is considered as efficient data structure in compare to arrays and linked lists. In searching process, it removes half sub-tree at every step. Searching for an element in a binary search tree takes o(log₂n) time. In worst case, the time it takes to search an element is 0(n).
3. It also speed up the insertion and deletion operations as compare to that in array and linked list.

Q. Create the binary search tree using the following data elements.

43, 10, 79, 90, 12, 54, 11, 9, 50

1. Insert 43 into the tree as the root of the tree.
2. Read the next element, if it is lesser than the root node element, insert it as the root of the left sub-tree.
3. Otherwise, insert it as the root of the right of the right sub-tree.

The process of creating BST by using the given elements, is shown in the image below.

Operations on Binary Search Tree

There are many operations which can be performed on a binary search tree.

SN	Operation	Description
1	Searching in BST	Finding the location of some specific element in a binary search tree.
2	Insertion in BST	Adding a new element to the binary search tree at the appropriate location so that the property of BST do not violate.
3	Deletion in BST	Deleting some specific node from a binary search tree. However, there can be various cases in deletion depending upon the number of children, the node have.

Program to implement BST operations

1. #include <iostream>  
2. #include <stdlib.h>  
3. using namespace std;  
4. struct Node {  
5.     int data;  
6.     Node *left;  
7.     Node *right;  
8. };  
9. Node* create(int item)  
10. {  
11.     Node* node = new Node;  
12.     node->data = item;  
13.     node->left = node->right = NULL;  
14.     return node;  
15. }  
16.   
17. void inorder(Node *root)  
18. {  
19.     if (root == NULL)  
20.         return;  
21.   
22.     inorder(root->left);  
23.     cout<< root->data << "   ";  
24.     inorder(root->right);  
25. }  
26. Node* findMinimum(Node* cur)  
27. {  
28.     while(cur->left != NULL) {  
29.         cur = cur->left;  
30.     }  
31.     return cur;  
32. }  
33. Node* insertion(Node* root, int item)  
34. {  
35.     if (root == NULL)  
36.         return create(item);  
37.     if (item < root->data)  
38.         root->left = insertion(root->left, item);  
39.     else  
40.         root->right = insertion(root->right, item);  
41.   
42.     return root;  
43. }  
44.   
45. void search(Node* &cur, int item, Node* &parent)  
46. {  
47.     while (cur != NULL && cur->data != item)  
48.     {  
49.         parent = cur;  
50.   
51.         if (item < cur->data)  
52.             cur = cur->left;  
53.         else  
54.             cur = cur->right;  
55.     }  
56. }  
57.   
58. void deletion(Node*& root, int item)  
59. {  
60.     Node* parent = NULL;  
61.     Node* cur = root;  
62.   
63.     search(cur, item, parent);  
64.     if (cur == NULL)  
65.         return;  
66.   
67.     if (cur->left == NULL && cur->right == NULL)  
68.     {  
69.         if (cur != root)  
70.         {  
71.             if (parent->left == cur)  
72.                 parent->left = NULL;  
73.             else  
74.                 parent->right = NULL;  
75.         }  
76.         else  
77.             root = NULL;  
78.   
79.         free(cur);       
80.     }  
81.     else if (cur->left && cur->right)  
82.     {  
83.         Node* succ  = findMinimum(cur- >right);  
84.   
85.         int val = succ->data;  
86.   
87.         deletion(root, succ->data);  
88.   
89.         cur->data = val;  
90.     }  
91.   
92.     else  
93.     {  
94.         Node* child = (cur->left)? Cur- >left: cur->right;  
95.   
96.         if (cur != root)  
97.         {  
98.             if (cur == parent->left)  
99.                 parent->left = child;  
100.             else  
101.                 parent->right = child;  
102.         }  
103.   
104.         else  
105.             root = child;  
106.         free(cur);  
107.     }  
108. }  
109.   
110. int main()  
111. {  
112.    Node* root = NULL;  
113.    int keys[8];  
114.    for(int i=0;i<8;i++)  
115.     {  
116.     cout << "Enter value to be inserted";  
117.     cin>>keys[i];  
118.         root = insertion(root, keys[i]);  
119.     }  
120.   
121.     inorder(root);  
122.     cout<<"\n";  
123.     deletion(root, 10);  
124.     inorder(root);  
125.     return 0;  
126. }  

Output:

Enter value to be inserted? 10
Enter value to be inserted? 20
Enter value to be inserted? 30
Enter value to be inserted? 40
Enter value to be inserted?  5 
Enter value to be inserted? 25
Enter value to be inserted? 15
Enter value to be inserted?  5

5 5 10 15 20 25 30 40 
5 5 15 20 25 30 40