fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct Node{
  5. 	int data;
  6. 	struct Node *left;
  7. 	struct Node *right;
  8. };
  9.  
  10. class BinarySearchTree{
  11. 	public:
  12. 	struct Node *root;
  13.  
  14. 	BinarySearchTree(){
  15. 		root = NULL;
  16. 	}
  17.  
  18. 	Node *getNode(int val){
  19. 		Node *newNode = new Node;
  20.  
  21. 		newNode->data = val;
  22. 		newNode->left = newNode->right = NULL;
  23.  
  24. 		return newNode;
  25. 	}
  26.  
  27. 	void insert(int &val){
  28. 		if(!root){
  29. 			root = getNode(val);
  30. 			return;
  31. 		}
  32.  
  33. 		insertHelper(root, NULL, val, false);
  34. 	}
  35.  
  36. 	void insertHelper(Node *rt, Node *parent, int &val, bool isLeft){
  37.  
  38. 		if(!rt){
  39. 			isLeft ? parent->left = getNode(val) : parent->right = getNode(val);
  40. 			return;
  41. 		}
  42.  
  43. 		if(val < rt->data)
  44. 			insertHelper(rt->left, rt, val, true);
  45. 		else 
  46. 			insertHelper(rt->right, rt, val, false);
  47. 	}
  48.  
  49. 	void searchNode(Node *rt, int &val){
  50. 		if(!rt || rt->data == val){
  51. 			cout<<"Element "<<val<<(rt ? " ": " not ")<<"found in the tree.\n";
  52. 			return;
  53. 		}
  54.  
  55. 		if(val < rt->data)
  56. 			searchNode(rt->left, val);
  57. 		else
  58. 			searchNode(rt->right, val);
  59. 	}
  60.  
  61. 	bool deleteNode(int &val){
  62. 		Node *rt = root;
  63.  
  64. 		if(!rt)
  65. 			return false;
  66.  
  67. 		if(rt->data == val){
  68. 			if(!rt->left && !rt->right)
  69. 				root = NULL;
  70. 			else if(!rt->left)
  71. 				root = rt->right;
  72. 			else if(!rt->right)
  73. 				root = rt->left;
  74. 			else
  75. 				return deleteNodeHelper(rt, NULL, val, false);
  76.  
  77. 			delete rt;
  78. 			return true;
  79. 		}
  80.  
  81. 		return deleteNodeHelper(rt, NULL, val, false);
  82. 	}
  83.  
  84. 	bool deleteNodeHelper(Node *rt, Node *parent, int &val, bool isLeft){
  85. 		if(!rt)
  86. 			return false;
  87.  
  88. 		if(rt->data == val){
  89.  
  90. 			if(!rt->left && !rt->right){
  91. 				isLeft ? parent->left = NULL : parent->right = NULL;
  92. 				delete rt;
  93. 			}
  94. 			else if(!rt->left){
  95. 				isLeft ? parent->left = rt->right : parent->right = rt->right;
  96. 				delete rt;
  97. 			}
  98. 			else if(!rt->right){
  99. 				isLeft ? parent->left = rt->left : parent->right = rt->left;
  100. 				delete rt;
  101. 			}
  102. 			else{
  103. 				Node *minNode = min(rt->right);
  104. 				rt->data = minNode->data;
  105. 				deleteNodeHelper(rt->right, rt, rt->data, false);
  106. 			}
  107. 			return true;
  108. 		}
  109.  
  110. 		if(val < rt->data)
  111. 			return deleteNodeHelper(rt->left, rt, val, true);
  112.  
  113. 		return deleteNodeHelper(rt->right, rt, val, false);
  114. 	}
  115.  
  116. 	Node *min(Node *rt){
  117. 		if(!rt->left){
  118. 			return rt;
  119. 		}
  120.  
  121. 		return min(rt->left);
  122. 	}
  123.  
  124. 	Node *max(Node *rt){
  125. 		if(!rt->right){
  126. 			return rt;
  127. 		}
  128.  
  129. 		return max(rt->right);
  130. 	}
  131.  
  132. 	void inOrder(Node *rt){
  133. 		if(!rt)
  134. 			return;
  135.  
  136. 		inOrder(rt->left);
  137. 		cout<<rt->data<<" ";
  138. 		inOrder(rt->right);
  139. 	}
  140.  
  141. 	void postOrder(Node *rt){
  142. 		if(!rt)
  143. 			return;
  144.  
  145. 		postOrder(rt->left);
  146. 		postOrder(rt->right);
  147. 		cout<<rt->data<<" ";
  148. 	}
  149.  
  150. 	void preOrder(Node *rt){
  151. 		if(!rt)
  152. 			return;
  153.  
  154. 		cout<<rt->data<<" ";
  155. 		preOrder(rt->left);
  156. 		preOrder(rt->right);
  157. 	}
  158.  
  159. 	void insertSortedArray(int *arr, int n){
  160. 		int low = 0, high = n-1;
  161.  
  162. 		root = insertSortedArrayHelper(arr, low, high);
  163. 	}
  164.  
  165. 	Node *insertSortedArrayHelper(int *a, int l, int h){
  166. 		if(l > h)
  167. 			return NULL;
  168.  
  169. 		int mid = l + (h-l)/2;
  170.  
  171. 		Node *rt = getNode(a[mid]);
  172.  
  173. 		rt->left = insertSortedArrayHelper(a, l, mid-1);
  174. 		rt->right = insertSortedArrayHelper(a, mid+1, h);
  175.  
  176. 		return rt;
  177. 	}
  178. };
  179.  
  180. int main(){
  181.  
  182. 	int opt, val;
  183. 	int *arr;
  184.  
  185. 	BinarySearchTree tree;
  186.  
  187. 	cout<<"Operations available on BST are:\n";
  188. 	cout<<"1. Insert an element\n2. Insert sorted array of elements\n"
  189. 	"3. Search an element\n4. Delete an element\n5. Minimum element in tree\n"
  190. 	"6. Maximum element in tree\n7. InOrder\n8. PreOrder\n9. PostOrder\n10. Exit\n";
  191. 	cout<<"************************************************\n";
  192. 	while(true){
  193. 		cin>>opt;
  194. 		switch(opt){
  195. 			case 1:
  196. 				cin>>val;
  197. 				tree.insert(val);
  198. 				cout<<"Element "<<val<<" is inserted into the tree.\n";
  199. 				break;
  200. 			case 2:
  201. 				cin>>opt;
  202. 				arr = new int[opt];
  203. 				cout<<"Sorted array elements ";
  204. 				for(int i=0; i<opt; ++i){ 
  205. 					cin>>arr[i]; cout<<arr[i]<<" ";
  206. 				}
  207. 				tree.insertSortedArray(arr, opt);
  208. 				cout<<"are inserted into the tree.\n";
  209. 				break;
  210. 			case 3:
  211. 				cin>>val;
  212. 				tree.searchNode(tree.root, val);
  213. 				break;
  214. 			case 4:
  215. 				cin>>val;
  216. 				cout<<"Element "<<val<<(tree.deleteNode(val) ? " is deleted\n": " not found for delete.\n");
  217. 				break;
  218. 			case 5:
  219. 				cout<<"The minimum element in the BST is: "<<tree.min(tree.root)->data<<"\n";
  220. 				break;
  221. 			case 6:
  222. 				cout<<"The maximum element in the BST is: "<<tree.max(tree.root)->data<<"\n";
  223. 				break;
  224. 			case 7:
  225. 				cout<<"InOrder: ";
  226. 				tree.inOrder(tree.root); cout<<"\n";
  227. 				break;
  228. 			case 8:
  229. 				cout<<"PreOrder: ";
  230. 				tree.preOrder(tree.root); cout<<"\n";
  231. 				break;
  232. 			case 9:
  233. 				cout<<"PostOrder: ";
  234. 				tree.postOrder(tree.root); cout<<"\n";
  235. 				break;
  236. 			case 10:
  237. 				exit(0);
  238. 		}
  239. 		cout<<"************************************************\n";
  240. 	}
  241.  
  242. 	return 0;
  243. }
Success #stdin #stdout 0s 4440KB
comments (?)
stdin
copy 
2
10
2 5 7 9 10 12 15 18 23 35
5 6
7 8 9
1 5
1 3
1 2
1 1
1 4
1 9
1 7
1 6
1 8
1 12
1 11
1 10
1 13
3 23
3 8
7 8 9
4 4
4 5
4 42
5 6
7 8 9 10
stdout
copy 
Operations available on BST are:
1. Insert an element
2. Insert sorted array of elements
3. Search an element
4. Delete an element
5. Minimum element in tree
6. Maximum element in tree
7. InOrder
8. PreOrder
9. PostOrder
10. Exit
************************************************
Sorted array elements 2 5 7 9 10 12 15 18 23 35 are inserted into the tree.
************************************************
The minimum element in the BST is: 2
************************************************
The maximum element in the BST is: 35
************************************************
InOrder: 2 5 7 9 10 12 15 18 23 35 
************************************************
PreOrder: 10 5 2 7 9 18 12 15 23 35 
************************************************
PostOrder: 2 9 7 5 15 12 35 23 18 10 
************************************************
Element 5 is inserted into the tree.
************************************************
Element 3 is inserted into the tree.
************************************************
Element 2 is inserted into the tree.
************************************************
Element 1 is inserted into the tree.
************************************************
Element 4 is inserted into the tree.
************************************************
Element 9 is inserted into the tree.
************************************************
Element 7 is inserted into the tree.
************************************************
Element 6 is inserted into the tree.
************************************************
Element 8 is inserted into the tree.
************************************************
Element 12 is inserted into the tree.
************************************************
Element 11 is inserted into the tree.
************************************************
Element 10 is inserted into the tree.
************************************************
Element 13 is inserted into the tree.
************************************************
Element 23 found in the tree.
************************************************
Element 8 found in the tree.
************************************************
InOrder: 1 2 2 3 4 5 5 6 7 7 8 9 9 10 10 11 12 12 13 15 18 23 35 
************************************************
PreOrder: 10 5 2 1 3 2 4 7 5 6 9 7 8 9 18 12 11 10 15 12 13 23 35 
************************************************
PostOrder: 1 2 4 3 2 6 5 8 7 9 9 7 5 10 11 13 12 15 12 35 23 18 10 
************************************************
Element 4 is deleted
************************************************
Element 5 is deleted
************************************************
Element 42 not found for delete.
************************************************
The minimum element in the BST is: 1
************************************************
The maximum element in the BST is: 35
************************************************
InOrder: 1 2 2 3 5 6 7 7 8 9 9 10 10 11 12 12 13 15 18 23 35 
************************************************
PreOrder: 10 5 2 1 3 2 7 6 9 7 8 9 18 12 11 10 15 12 13 23 35 
************************************************
PostOrder: 1 2 3 2 6 8 7 9 9 7 5 10 11 13 12 15 12 35 23 18 10 
************************************************
https://ideone.com/AxYbv4
Binary Search Tree with sorted array input
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!