1. #include<stdio.
h>
2. #include<stdlib.h>
3. struct node
4. {
5. int info;
6. struct node*left;
7. struct node*right;
8. };
9. typedef struct node BST;
10. BST *LOC, *PAR;
11. void search(BST *root, int item)
12. {
13. BST *save,*ptr;
14. if (root == NULL)
15. {
16. LOC = NULL;
17. PAR=NULL;
18. }
19. if (item == root -> info)
20. {
21. LOC = root;
22. PAR = NULL;
23. return;
24. }
25. if (item < root->info)
26. {
27. save = root;
28. ptr = root->left;
29. }
30. else
31. {
32. save = root;
33. ptr = root -> right;
34. }
35. while( ptr != NULL)
36. {
37. if (ptr -> info == item)
38. {
39. LOC = ptr;
40. PAR = save;
41. return;
42. }
43. if(item < ptr->info)
44. {
45. save = ptr;
46. ptr = ptr->left;
47. }
48. else
49. {
50. save = ptr;
51. ptr = ptr->right;
52. }
53. }
54. LOC = NULL;
55. PAR = save;
56. return;
57. }
58.
59. struct node* findmin(struct node*r)
60. {
61. if (r == NULL)
62. return NULL;
63. else if (r->left!=NULL)
64. return findmin(r->left);
65. else if (r->left == NULL)
66. return r;
67. }
68. struct node*insert(struct node*r, int x)
69. {
70. if (r == NULL)
71. {
72. r = (struct node*)malloc(sizeof(struct node));
73. r->info = x;
74. r->left = r->right = NULL;
75. return r;
76. }
77. else if (x < r->info)
78. r->left = insert(r->left, x);
79. else if (x > r->info)
80. r->right = insert(r->right, x);
81. return r;
82. }
83.
84. struct node* del(struct node*r, int x)
85. {
86. struct node *t;
87. if(r == NULL)
88. printf("\nElement not found");
89. else if (x < r->info)
90. r->left = del(r->left, x);
91. else if (x > r->info)
92. r->right = del(r->right, x);
93. else if ((r->left != NULL) && (r->right != NULL))
94. {
95. t = findmin(r->right);
96. r->info = t->info;
97. r->right = del(r->right, r->info);
98. }
99. else
100. {
101. t = r;
102. if (r->left == NULL)
103. r = r->right;
104. else if (r->right == NULL)
105. r = r->left;
106. free(t);
107. }
108. return r;
109. }
110.
111.
112. int main()
113. {
114. struct node* root = NULL;
115. int x, c = 1, z;
116. int element;
117. char ch;
118. printf("\nEnter an element: ");
119. scanf("%d", &x);
120. root = insert(root, x);
121. printf("\nDo you want to enter another element :y or n");
122. scanf(" %c",&ch);
123. while (ch == 'y')
124. {
125. printf("\nEnter an element:");
126. scanf("%d", &x);
127. root = insert(root,x);
128. printf("\nPress y or n to insert another element: y or n: ");
129. scanf(" %c", &ch);
130. }
131. while(1)
132. {
133. printf("\n1 Insert an element ");
134. printf("\n2 Delete an element");
135. printf("\n3 Search for an element ");
136. printf("\n4 Exit ");
137. printf("\nEnter your choice: ");
138. scanf("%d", &c);
139. switch(c)
140. {
141. case 1:
142. printf("\nEnter the item:");
143. scanf("%d", &z);
144. root = insert(root,z);
145. break;
146. case 2:
147. printf("\nEnter the info to be deleted:");
148. scanf("%d", &z);
149. root = del(root, z);
150. break;
151. case 3:
152. printf("\nEnter element to be searched: ");
153. scanf("%d", &element);
154. search(root, element);
155. if(LOC != NULL)
156. printf("\n%d Found in Binary Search Tree !!\n",element);
157. else
158. printf("\nIt is not present in Binary Search Tree\n");
159. break;
160. case 4:
161. printf("\nExiting...");
162. return;
163. default:
164. printf("Enter a valid choice: ");
165.
166. }
167. }
168. return 0;
169. }
