API tools faq
paste
Advertisement
maycod23

Untitled

maycod23
Apr 17th, 2022
73
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.75 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<int> v;
  4. class bst
  5. {
  6. public:
  7. int data;
  8. bst* left;
  9. bst* right;
  10. bst(int data)
  11. {
  12. this->data = data;
  13. left = NULL;
  14. right = NULL;
  15. }
  16. };
  17.  
  18. bst* insert(bst* root, int item)
  19. {
  20. if (root == NULL)
  21. {
  22. bst* NODE = new bst(item);
  23. return NODE;
  24. }
  25. if (item < root->data)
  26. {
  27. root->left = insert(root->left, item);
  28. }
  29. if (item > root->data)
  30. {
  31. root->right = insert(root->right, item);
  32. }
  33. return root;
  34. }
  35. bst* deletekar(bst* root, int item)
  36. {
  37. if (root == NULL)
  38. {
  39. return NULL;
  40. }
  41. if (item < root->data)
  42. {
  43. root->left = deletekar(root->left, item);
  44. }
  45. if (item > root->data)
  46. {
  47. root->right = deletekar(root->right, item);
  48. }
  49. if (item == root->data)
  50. {
  51. if (root->left == NULL && root->right == NULL)
  52. {
  53. delete(root);
  54. return NULL;
  55. }
  56. else if (root->left == NULL)
  57. {
  58. bst* k = new bst(root->right->data);
  59. delete(root);
  60. return k;
  61. }
  62. else if (root->right == NULL)
  63. {
  64. bst* k = new bst(root->left->data);
  65. delete(root);
  66. return k;
  67. }
  68. else
  69. {
  70. bst* joy = root->right;
  71. while (joy->left != NULL)
  72. {
  73. joy = joy->left;
  74. }
  75. root->data = joy->data; //swapping done
  76. //delete joy from right;
  77. root->right = deletekar(root->right, joy->data);
  78. /////////////////////2nd approach////////////////////////
  79. bst* succParent = root;
  80. bst* succ = root->right;
  81. while (succ->left != NULL)
  82. {
  83. succParent = succ;
  84. succ = succ->left;
  85. }
  86. if (succParent != root)
  87. succParent->left = succ->right;
  88. else
  89. succParent->right = succ->right;
  90. root->data = succ->data;
  91. delete succ;
  92. }
  93. }
  94. return root;
  95. }
  96. void printPostorder(bst* node)
  97. {
  98. if (node == NULL)
  99. return;
  100. printPostorder(node->left);
  101. printPostorder(node->right);
  102. cout << node->data << " ";
  103. }
  104.  
  105. void printInorder(bst* node)
  106. {
  107. if (node == NULL)
  108. return;
  109. printInorder(node->left);
  110. cout << node->data << " ";
  111. printInorder(node->right);
  112. }
  113.  
  114. void printPreorder(bst* node)
  115. {
  116. if (node == NULL)
  117. return;
  118. cout << node->data << " ";
  119. printPreorder(node->left);
  120. printPreorder(node->right);
  121. }
  122.  
  123. bool search(bst* root, int item)
  124. {
  125. if (root == NULL)
  126. {
  127. return false;
  128. }
  129. if (root->data == item)
  130. {
  131. return true;
  132. }
  133. if (item < root->data)
  134. {
  135. return search(root->left, item);
  136. }
  137. return search(root->right, item);
  138. }
  139.  
  140. int findmin(bst* root)
  141. {
  142. while (root->left != NULL)
  143. {
  144. root = (root->left);
  145. }
  146. return root->data;
  147. }
  148.  
  149. int findmax(bst* root)
  150. {
  151. while (root->right != NULL)
  152. {
  153. root = (root->right);
  154. }
  155. return root->data;
  156. }
  157. void levelorder(bst* root)
  158. {
  159. if (root == NULL) return;
  160. queue<bst*> q;
  161. q.push(root);
  162. while (q.size() != 0)
  163. {
  164. int count = q.size();
  165. while (count > 0)
  166. {
  167. bst* node = q.front();
  168. cout << node->data << " ";
  169. q.pop();
  170. if (node->left != NULL) q.push(node->left);
  171. if (node->right != NULL) q.push(node->right);
  172. count--;
  173. }
  174. cout << endl;
  175. }
  176. }
  177. int main()
  178. {
  179. bst* root = NULL;
  180. // cout << sizeof(NULL) << endl;
  181. root = insert(root, 6);
  182. root = insert(root, 3);
  183. root = insert(root, 5);
  184. root = insert(root, 2);
  185. root = insert(root, 8);
  186. root = insert(root, 7);
  187. root = insert(root, 9);
  188. // printPostorder(root);
  189. // cout << endl;
  190. // printPreorder(root);
  191. // cout << endl;
  192. levelorder(root);
  193. // for (int i = 0; i < v.size(); i++)
  194. // {
  195. // cout << v[i] << endl;
  196. // }
  197. // cout << endl;
  198. // if (search(root, 6)) cout << "Found" << endl;
  199. // else cout << "Not Found" << endl;
  200. // cout << "findmin " << findmin(root) << " " << endl;
  201. // cout << "findmax " << findmax(root) << " " << endl;
  202. return 0;
  203. }
  204.  
  205.  
  206. //////////////////////////////////////////////////////////////////////////////////////
  207. //////////////////////////////////////////////////////////////////////////////////////
  208. //////////////////////////////////////////////////////////////////////////////////////
  209. //////////////////////////////////////////////////////////////////////////////////////
  210. //////////////////////////////////////////////////////////////////////////////////////
  211. ///////////leetcode level order traversal level wise//////////////////////////////////
  212. //////////////////////////////////////////////////////////////////////////////////////
  213. //////////////////////////////////////////////////////////////////////////////////////
  214. //////////////////////////////////////////////////////////////////////////////////////
  215. //////////////////////////////////////////////////////////////////////////////////////
  216. //////////////////////////////////////////////////////////////////////////////////////
  217. //////////////////////////////////////////////////////////////////////////////////////
  218. //////////////////////////////////////////////////////////////////////////////////////
  219. //////////////////////////////////////////////////////////////////////////////////////
  220. /**
  221. * Definition for a binary tree node.
  222. * struct TreeNode {
  223. * int val;
  224. * TreeNode *left;
  225. * TreeNode *right;
  226. * TreeNode() : val(0), left(nullptr), right(nullptr) {}
  227. * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  228. * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  229. * };
  230. */
  231. // class Solution
  232. // {
  233. // public:
  234. // vector<vector<int>> levelOrder(TreeNode* root)
  235. // {
  236. // vector<vector<int>> v;
  237. // if (root == NULL) return v;
  238. // queue<TreeNode*> q;
  239. // q.push(root);
  240. // int i=0;
  241. // while (q.size()!=0)
  242. // {
  243. // int nodeCount = q.size();
  244. // vector<int> temp;
  245. // while (nodeCount > 0)
  246. // {
  247. // TreeNode* node = q.front();
  248. // q.pop();
  249. // temp.push_back(node->val);
  250. // if (node->left != NULL)
  251. // q.push(node->left);
  252. // if (node->right != NULL)
  253. // q.push(node->right);
  254. // nodeCount--;
  255. // }
  256. // v.push_back(temp);
  257. // temp.clear();
  258. // }
  259. // return v;
  260. // }
  261. // };
  262.  
  263.  
  264.  
  265.  
  266. ////////////////////////////////////////////////////////////////////////////////////////////
  267. //////////////////////////////////////////////////////////////////////////////////////
  268. // #include<bits/stdc++.h>
  269. // using namespace std;
  270. // class bst {
  271. // public:
  272. // int data;
  273. // bst* left;
  274. // bst* right;
  275. // bst(int data)
  276. // {
  277. // this->data = data;
  278. // right = NULL;
  279. // left = NULL;
  280. // }
  281. // };
  282. // bst* insert(bst* root, int item)
  283. // {
  284. // if (root == NULL)
  285. // {
  286. // bst* node = new bst(item);
  287. // return node;
  288. // }
  289. // if (item < root->data)
  290. // {
  291. // root->left = insert(root->left, item);
  292. // }
  293. // if (item > root->data)
  294. // {
  295. // root->right = insert(root->right, item);
  296. // }
  297. // return root;
  298. // }
  299. // bool search(bst* root, int item)
  300. // {
  301. // if (root == NULL)
  302. // {
  303. // return false;
  304. // }
  305. // if (root->data == item)
  306. // {
  307. // return true;
  308. // }
  309. // if (item < root->data)
  310. // {
  311. // return search(root->left, item);
  312. // }
  313. // return search(root->right, item);
  314. // }
  315. // void inorder(bst* root)
  316. // {
  317. // if (root == NULL) return;
  318. // inorder(root->left);
  319. // cout << root->data << " ";
  320. // inorder(root->right);
  321. // }
  322. // bst* deletekar(bst* root, int item)
  323. // {
  324. // if (root == NULL)
  325. // {
  326. // return NULL;
  327. // }
  328. // if (item < root->data)
  329. // {
  330. // root->left = deletekar(root->left, item);
  331. // }
  332. // if (item > root->data)
  333. // {
  334. // root->right = deletekar(root->right, item);
  335. // }
  336. // if (item == root->data)
  337. // {
  338. // if (root->left == NULL && root->right == NULL)
  339. // {
  340. // delete(root);
  341. // return NULL;
  342. // }
  343. // else if (root->left == NULL)
  344. // {
  345. // bst* k = new bst(root->right->data);
  346. // delete(root);
  347. // return k;
  348. // }
  349. // else if (root->right == NULL)
  350. // {
  351. // bst* k = new bst(root->left->data);
  352. // delete(root);
  353. // return k;
  354. // }
  355. // else
  356. // {
  357. // bst* joy = root->right;
  358. // while (joy->left != NULL)
  359. // {
  360. // joy = joy->left;
  361. // }
  362. // root->data = joy->data; //swapping done
  363. // //delete joy from right;
  364. // root->right = deletekar(root->right, joy->data);
  365. // }
  366. // }
  367. // return root;
  368. // }
  369. // int main()
  370. // {
  371. // bst* root = NULL;
  372. // root = insert(root, 18);
  373. // root = insert(root, 88);
  374. // root = insert(root, 83);
  375. // root = insert(root, 34);
  376. // root = insert(root, 6);
  377. // root = insert(root, 8);
  378. // root = insert(root, 21);
  379. // root = insert(root, 13);
  380. // root = insert(root, 19);
  381. // inorder(root);
  382. // if (search(root, 9)) cout << "found" << endl;
  383. // else cout << "not found" << endl;
  384. // root = deletekar(root, 18);
  385. // inorder(root);
  386. // }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!