assignment_16.cpp (10249B)
1 /* WAP to create a Binary Search Tree and include following operations in tree: i. Insertion (Recursive and Iterative Implementation) ii. Deletion by copying iii. Deletion by Merging iv. Search a no. in BST v. Display its preorder, postorder and inorder traversals Recursively vi. Display its preorder, postorder and inorder traversals Iteratively vii. Display its level-by-level traversals viii. Count the non-leaf nodes and leaf nodes ix. Display height of tree x. Create a mirror image of tree xi. Check whether two BSTs are equal or not */ 2 3 #include <iostream> 4 #include <stack> 5 #include <queue> 6 #include <algorithm> 7 8 using namespace std; 9 10 struct node { 11 int data; 12 node *left; 13 node *right; 14 15 node(int val) : data(val), left(nullptr), right(nullptr) {} 16 }; 17 18 class BST { 19 private: 20 node *root; 21 22 node* insertRecursive(node *current, int val) { 23 if (current == nullptr) return new node(val); 24 if (val < current->data) current->left = insertRecursive(current->left, val); 25 else if (val > current->data) current->right = insertRecursive(current->right, val); 26 else cout << "Duplicate value ignored.\n"; 27 return current; 28 } 29 30 node* deleteByCopying(node *current, int key, bool &found) { 31 if (current == nullptr) return nullptr; 32 if (key < current->data) { 33 current->left = deleteByCopying(current->left, key, found); 34 } else if (key > current->data) { 35 current->right = deleteByCopying(current->right, key, found); 36 } else { 37 found = true; 38 if (current->left == nullptr) { node *temp = current->right; delete current; return temp; } 39 if (current->right == nullptr) { node *temp = current->left; delete current; return temp; } 40 node *pred = current->left; 41 while (pred->right != nullptr) pred = pred->right; 42 current->data = pred->data; 43 current->left = deleteByCopying(current->left, pred->data, found); 44 } 45 return current; 46 } 47 48 node* deleteByMerging(node *current, int key, bool &found) { 49 if (current == nullptr) return nullptr; 50 if (key < current->data) { current->left = deleteByMerging(current->left, key, found); return current; } 51 if (key > current->data) { current->right = deleteByMerging(current->right, key, found); return current; } 52 found = true; 53 if (current->left == nullptr) { node *temp = current->right; delete current; return temp; } 54 if (current->right == nullptr) { node *temp = current->left; delete current; return temp; } 55 node *successor = current->right; 56 while (successor->left != nullptr) successor = successor->left; 57 successor->left = current->left; 58 node *temp = current->right; 59 delete current; 60 return temp; 61 } 62 63 int countLeaf(node *current) const { 64 if (current == nullptr) return 0; 65 if (current->left == nullptr && current->right == nullptr) return 1; 66 return countLeaf(current->left) + countLeaf(current->right); 67 } 68 69 int countNonLeaf(node *current) const { 70 if (current == nullptr || (current->left == nullptr && current->right == nullptr)) return 0; 71 return 1 + countNonLeaf(current->left) + countNonLeaf(current->right); 72 } 73 74 int height(node *current) const { 75 if (current == nullptr) return -1; 76 return 1 + max(height(current->left), height(current->right)); 77 } 78 79 void mirror(node *current) { 80 if (current == nullptr) return; 81 swap(current->left, current->right); 82 mirror(current->left); 83 mirror(current->right); 84 } 85 86 bool areEqual(node *root1, node *root2) const { 87 if (!root1 && !root2) return true; 88 if (!root1 || !root2 || root1->data != root2->data) return false; 89 return areEqual(root1->left, root2->left) && areEqual(root1->right, root2->right); 90 } 91 92 void destroy(node *current) { 93 if (current == nullptr) return; 94 destroy(current->left); 95 destroy(current->right); 96 delete current; 97 } 98 99 void preorderRecursive(node *current) const { 100 if (!current) return; 101 cout << current->data << " "; 102 preorderRecursive(current->left); 103 preorderRecursive(current->right); 104 } 105 106 void inorderRecursive(node *current) const { 107 if (!current) return; 108 inorderRecursive(current->left); 109 cout << current->data << " "; 110 inorderRecursive(current->right); 111 } 112 113 void postorderRecursive(node *current) const { 114 if (!current) return; 115 postorderRecursive(current->left); 116 postorderRecursive(current->right); 117 cout << current->data << " "; 118 } 119 120 public: 121 BST() : root(nullptr) {} 122 BST(const BST &other) = delete; 123 BST& operator=(const BST &other) = delete; 124 ~BST() { destroy(root); } 125 126 void insertRecursive(int val) { root = insertRecursive(root, val); } 127 128 void insertIterative(int val) { 129 node *newNode = new node(val); 130 if (root == nullptr) { root = newNode; return; } 131 node *current = root, *parent = nullptr; 132 while (current != nullptr) { 133 parent = current; 134 if (val < current->data) current = current->left; 135 else if (val > current->data) current = current->right; 136 else { cout << "Duplicate value ignored.\n"; delete newNode; return; } 137 } 138 if (val < parent->data) parent->left = newNode; 139 else parent->right = newNode; 140 } 141 142 void deleteCopying(int key) { 143 bool found = false; 144 root = deleteByCopying(root, key, found); 145 if (!found) cout << "Element not found in BST.\n"; 146 } 147 148 void deleteMerging(int key) { 149 bool found = false; 150 root = deleteByMerging(root, key, found); 151 if (!found) cout << "Element not found in BST.\n"; 152 } 153 154 bool search(int key) const { 155 node *current = root; 156 while (current != nullptr) { 157 if (current->data == key) return true; 158 current = (key < current->data) ? current->left : current->right; 159 } 160 return false; 161 } 162 163 void preorderRecursive() const { preorderRecursive(root); cout << "\n"; } 164 void inorderRecursive() const { inorderRecursive(root); cout << "\n"; } 165 void postorderRecursive() const { postorderRecursive(root); cout << "\n"; } 166 167 void preorderIterative() const { 168 if (!root) return; 169 stack<node*> s; 170 s.push(root); 171 while (!s.empty()) { 172 node *curr = s.top(); s.pop(); 173 cout << curr->data << " "; 174 if (curr->right) s.push(curr->right); 175 if (curr->left) s.push(curr->left); 176 } 177 cout << "\n"; 178 } 179 180 void inorderIterative() const { 181 stack<node*> s; 182 node *curr = root; 183 while (curr != nullptr || !s.empty()) { 184 while (curr != nullptr) { s.push(curr); curr = curr->left; } 185 curr = s.top(); s.pop(); 186 cout << curr->data << " "; 187 curr = curr->right; 188 } 189 cout << "\n"; 190 } 191 192 void postorderIterative() const { 193 if (!root) return; 194 stack<node*> s1, s2; 195 s1.push(root); 196 while (!s1.empty()) { 197 node *curr = s1.top(); s1.pop(); 198 s2.push(curr); 199 if (curr->left) s1.push(curr->left); 200 if (curr->right) s1.push(curr->right); 201 } 202 while (!s2.empty()) { cout << s2.top()->data << " "; s2.pop(); } 203 cout << "\n"; 204 } 205 206 void levelOrder() const { 207 if (!root) return; 208 queue<node*> q; 209 q.push(root); 210 while (!q.empty()) { 211 node *curr = q.front(); q.pop(); 212 cout << curr->data << " "; 213 if (curr->left) q.push(curr->left); 214 if (curr->right) q.push(curr->right); 215 } 216 cout << "\n"; 217 } 218 219 void countNodes() const { 220 cout << "Leaf Nodes: " << countLeaf(root) << "\n"; 221 cout << "Non-Leaf Nodes: " << countNonLeaf(root) << "\n"; 222 } 223 224 void displayHeight() const { cout << "Height of Tree: " << height(root) << "\n"; } 225 void createMirror() { mirror(root); } 226 bool isEqual(const BST &other) const { return areEqual(root, other.root); } 227 }; 228 229 int main() { 230 BST tree; 231 int choice, value; 232 233 while (true) { 234 cout << "1.InsertRec 2.InsertIter 3.DeleteCopy 4.DeleteMerge 5.Search\n"; 235 cout << "6.PreorderRec 7.InorderRec 8.PostorderRec 9.PreorderIter 10.InorderIter\n"; 236 cout << "11.PostorderIter 12.LevelOrder 13.CountNodes 14.Height 15.Mirror 16.CheckEqual 0.Exit\n"; 237 cout << "Enter your choice: "; 238 cin >> choice; 239 240 switch (choice) { 241 case 1: cout << "Enter value: "; cin >> value; tree.insertRecursive(value); break; 242 case 2: cout << "Enter value: "; cin >> value; tree.insertIterative(value); break; 243 case 3: cout << "Enter value to delete: "; cin >> value; tree.deleteCopying(value); break; 244 case 4: cout << "Enter value to delete: "; cin >> value; tree.deleteMerging(value); break; 245 case 5: 246 cout << "Enter value to search: "; cin >> value; 247 cout << (tree.search(value) ? "Found\n" : "Not found\n"); 248 break; 249 case 6: tree.preorderRecursive(); break; 250 case 7: tree.inorderRecursive(); break; 251 case 8: tree.postorderRecursive(); break; 252 case 9: tree.preorderIterative(); break; 253 case 10: tree.inorderIterative(); break; 254 case 11: tree.postorderIterative(); break; 255 case 12: tree.levelOrder(); break; 256 case 13: tree.countNodes(); break; 257 case 14: tree.displayHeight(); break; 258 case 15: tree.createMirror(); break; 259 case 16: { 260 BST tree2; 261 int n; 262 cout << "Enter number of nodes for second BST: "; cin >> n; 263 for (int i = 0; i < n; i++) { cin >> value; tree2.insertIterative(value); } 264 cout << (tree.isEqual(tree2) ? "Both BSTs are equal.\n" : "BSTs are not equal.\n"); 265 break; 266 } 267 case 0: return 0; 268 default: cout << "Wrong choice.\n"; 269 } 270 } 271 }