C++

BST Programming Challenges

- Provide your implementation for all the functions in the following exercises, as well as your implementation of main() inHW3.cpp. - Adding private functions (in BST.h only) is allowed but modifying anything else is not allowed - Do not add or remove any files.

Ex1. DLL2BST (15 points)

Add a constructor that constructs the binary search tree from the given DLList.

BST::BST(const DLList& list)

Ex2. Find the Second Minimum (25 points)

Write a member function called int BST::Find_Second_Minimum() const. The function retrieves the value of the node that has the second minimum value in the current BST. The second minimum is the element just greater than the minimum number. The running time of your implementation should be O(h).

Ex3. Get the Longest Path (25 points)

Write a member function called DLList BST::get_longest_path() that returns a DLList of the longest path in the tree. For example, the red nodes in the following tree are on the longest path and should be added to the list. In case there are multiple longest paths, retrieve any of them.

Ex4. Extract SubTree (25 points)

Write a BST member function BST BST::Copy_subTree(const T& n) that will extract and return the subtree rooted at the node containing the value n.

For example, on the following tree, the function should return the subtree shown to the right.

Ex5. New Traverse (Bonus 20 points)

Write a BST member function void BST::BFT() that will print the tree elements in the way that is shown in the next figure

Ex6. Main (10 points)

Write a main() function that tests the functions you implemented in exercises 1-5.

cpp file

BSTNode.H file

BST.h file

please help me

1 #include "BST.h" 2 #include 3 using namespace std; 4 5 BST::BST (const DLList&list) { 6} 7 8 int BST:: Find_Second_Minimum) 9 DLList BST::get_longest_path() 10 11 BST BST:: Copy_subTree(const T& n) 12 // Provide your solution for exercise 6 here // 13 14 int main() { 15 cout class BST; 3 template 4 class BSTNode{ 5 private: 6 I val; 7 BSTNode* left; BSTNodet right; 9 int depth; int height; 11 friend class BST; 12 public: 13 BSTNode (const T& V, BSTNodeleft, BSTNodet right); 14 -BSTNode(){}; I get_val() { return val;} BSTNode= getLeft() { return left; } 17 BSTNode* getRight() { return right; } 18 }; 10 15 16 19 20 template 21 BSTNode:: BSTNode(const T& V, BSTNodex left, BSTNodet right) { 22 val = v; 23 this->left: left; 24 this->right-right; 25 depth = height= -1; // Not computed yet 26 } 1 #pragma once 2 #include "BSTNode.h" 3 #include "DLList.h" 4 #include "QueueDLL.h" 5 #include "StackDLL.h" 6 7 template 8 class BST 9 { 10 public: 11 BST(); 12 BST (const BST& other); 13 -BST(); 14 bool is_empty() const; bool contains (const T& val) const; 15 16 17 18 19 20 21 22 23 I max() const; T min) const; I remove_max(); I remove_min(); 24 void insert(const T& val); bool remove(const T& val); void clear(); 25 26 27 28 29 DLList elements) const; DLList elements_level_ordered() const; BSTNode* get_root) const { return root; } 29 BSTNode* get_root() const { return root; } 30 BST& operator=(const BST& other); 31 // exercises 32 BST (const DLList& list); 33 int find_second_minimum) const; 34 DLList get_longest_path(); 35 void BFT(); 36 BST copy_subTree(const T& n); 37 private: 38 BSTNode #root; 39 void copy_from(BSTNode* node); 40 void elements (DLList& result, BSTNode* node) const; 41 bool contains (const T& val, BSTNode* node) const; 42 void del_single (BSTNode* ptr, BSTNode* prev); 43 void del_double (BSTNode* node); 44 void clear (BSTNode* node); 45 }; 46 template 47 BST::BST() 48 { 49 root = nullptr; 50 } 51 // uses pre-order traversal 52 template 53 void BST::copy_from(BSTNode* node) { 54 if (node == nullptr) 55 return; 56 insert(node->val); 10 63 56 insert(node->val); 57 copy_from(node->left); 58 copy_from(node->right); 59 ] 60 template 61 BST:: BST (const BST& other) { 62 root = nullptr; copy_from(other.root); 64 } 65 template 66 BST::-BST() 67 { 68 clear(); 69 } 70 template 71 bool BST::is_empty() const 72 { return root == nullptr; 74 } 75 template 76 bool BST:: contains (const T& val) const 77 { 78 BSTNode* node = root; // always start the search from the root while(node != nullptr) { // If the current node has the value we are looking for 81 if (val == node->val) 82 return true; 83 // If the value that we are looking for is smaller than the 84 // value of the current tree node, go left; else, go right 73 79 80 on 86 90 96 84 // value of the current tree node, go left; else, go right 85 if(val val) node = node->left; 87 else 88 node = node->right; 89 } return false; 91 } 92 template 93 bool BST:: contains (const T& val, BSTNode* node) const 94 { 95 // if a nullptr is reached, val does not exist in the tree if (node == nullptr) 97 return false; 98 // search value is found in the current node 99 if(val == node->val) 100 return true; 101 // search in either the left sub-tree or the right sub-tree, 102 1/ depending on the value of val 103 if(val val) 104 return contains (val, node->left); 105 else 106 return contains(val, node->right); 107 } 108 template 109 void BST:: insert(const T& val) 110 { 111 // if the tree is empty, the root needs to point at the new node. 112 if (is_empty() { 114 115 113 root = new BSTNode (val, nullptr, nullptr); return; } 116 BSTNode* curr = root; 117 BSTNode* prev = nullptr; 118 // Loop to search for the right position for val 119 while(curr != nullptr) 120 { 121 prev = curr; 122 if (val val) 123 curr = curr->left; 124 else if (val > curr->val) 125 curr = curr->right; 126 else 127 return; } 129 BSTNode* new_node = new BSTNode(val, nullptr, nullptr); 130 if (val val) 131 prev->left = new_node; 132 else 133 prev->right = new_node; 134 } 135 // Breadth-first traversal 136 template 137 DLList BST::elements_level_ordered) const 138 { 139 DLList result; 128 140 if (root == nullptr) 141 return result; 142 // a queue of pointers to BSTNode objects. 143 QueueDLL*> queue; 144 BSTNode* node = root; 145 queue. enq (node); 146 while (!queue.is_empty()) { 147 // Take a node out of the queue, process it and then insert 148 // its children into the queue. 149 node = queue.deq; 150 result.add_to_tail(node->val); 151 if (node->left != nullptr) 152 queue.eng (node->left); 153 if (node->right != nullptr) 154 queue.eng (node->right); 155 } 156 return result; 157 } 158 // returns the tree elements in-order 159 template 160 DLList BST::elements const 161 { 162 DLList result; 163 elements (result, root); 164 return result; 165 } 166 // recursive helper version: returns the elements in-order 167 template 167 template 168 void BST::elements (DLList& result, BSTNode* node) const 169 { 170 if (node == nullptr) 171 return; 172 elements (result, node->left); 173 // Process the node after processing its left subtree 174 // and before processing its right subtree 175 result.add_to_tail(node->val); 176 elements (result, node->right); 177 } 178 template 179 bool BST:: remove(const T& val) 180 { 181 BSTNode* node = root; 182 BSTNode* prev = nullptr; 183 if (is_empty()) 184 return false; 185 // This loop searches for the node to be deleted 186 while (node != nullptr) 187 { 188 if (node->val == val) 189 break; 190 prev = node; 191 if (val val) 192 node = node->left; 193 else 194 node = node->right; 195 } 198 199 195 } 196 // if node is not found, return false without deleting anything 197 if (node == nullptr) return false; // if the node has 0 or 1 children, call del_single() else call del_double() 200 if (node->left nullptr || node->right == nullptr) 201 del_single (node, prev); 202 else 203 del_double (node); 204 return true; 205 } 206 // Deletes a node with at most one child. 207 // This function is 0(1) in the best and worst case. 208 template 209 void BST::del_single (BSTNode* ptr, BSTNode* prev) 210 { 211 // if the node to be deleted is the root 212 if (ptr == root) { 213 // the new root becomes the child that is not null. 214 // if both children are null, the root becomes null. 215 if (root->left != nullptr) 216 root = root->left; 217 else 218 root = root->right; 219 } 220 // if the node to be deleted is the left child of its parent, 221 // set the parent's left child to the only child of the deleted node 222 // or to null if it has no children 223 222 // or to null if it has no children else if (ptr prev->left) { 224 if (ptr->right != nullptr) 225 prev->left = ptr->right; 226 else 227 prev->left = ptr->left; 228 } 229 // if the node to be deleted is the right child of its parent, 230 // set the parent's right child to the only child of the deleted node 231 // or to null if it has no children 232 else { 233 if (ptr->right != nullptr) 234 prev->right = ptr->right; 235 else 236 prev->right = ptr->left; 237 } 238 delete ptr; 239} 240 // Deletes a node with exactly two children. 241 // This function is o(height) in the worst case and 0(1) in the best case. 242 template 243 void BST::del_double (BSTNode* node) 244 { 245 // the replacement will be the largest node in the left subtree. 246 // So, start searching for a replacement by going left 247 BSTNode* rep = node->left; 248 BSTNode* prev = node; 249 // keep going right until a node with no right is reached. 250 // The largest node in the left subtree is the rightmost 250 // The largest node in the left subtree is the rightmost 251 // node in the left subtree. 252 while (rep->right != nullptr) { 253 prev = rep; 254 rep = rep->right; 255 } 256 // copy the value of the replacement into the node to be deleted 257 node->val = rep->val; 258 Il delete the replacement node using del_single, because that 259 // node does not have a right child. 260 del_single(rep, prev); 261 } 262 template 263 void BST::clear() 264 { 265 clear (root); 266 root = nullptr; 267 } 268 // Deleting nodes is best done in post-order, because we should not 269 // delete a node until we have deleted its left and its right. 270 template 271 void BST::clear (BSTNode* node) 272 { 273 if (node == nullptr) 274 return; 275 clear (node->left); 276 clear (node->right); 277 delete node; 278 ] 277 delete node; 278 } 279 // returns the maximum element in the tree. 280 // Asymptotic Complexity: 281 // * Best Case: 0(1) if the root is the maximum. 282 // * Worst Case: O(n) if the tree is a right-leaning chain. 283 template 284 T BST:: max() const { 285 if (is_empty()) 286 throw "Attempting to retrieve the max value in an empty tree"; 287 BSTNode* curr = root; 288 while (curr->right != nullptr) 289 curr = curr->right; 290 return curr->val; 291 ] 292 // returns the minimum element in the tree. 293 // Asymptotic Complexity: 294 // + Best Case: 0(1) if the root is the minimum. 295 // * Worst Case: 0(n) if the tree is a left-leaning chain. 296 template 297 T BST::min) const { 298 if (is_empty()) 299 throw "Attempting to retrieve the min value in an empty tree"; 300 BSTNode* curr = root; 301 while (curr->left != nullptr) 302 curr = curr->left; 303 304 return curr->val; 305 ] 305 ] 306 // removes and returns the maximum value in the tree. 307 template 308 T BST::remove_max() { 309 if (is_empty()) 310 throw "Attempting to remove the max value from an empty tree"; 311 BSTNode* curr = root; 312 BSTNode* prev = nullptr; 313 while (curr->right != nullptr) { 314 prev = curr; 315 curr = curr->right; 316 } 317 I val = curr->val; 318 del_single(curr, prev); 319 return val; 320 ] 321 // removes and returns the minimum value in the tree. 322 template 323 I BST::remove_min() { 324 if (is_empty()) 325 throw "Attempt the min value from an empty tree"; 326 BSTNode* curr = root; 327 BSTNode* prev = nullptr; 328 while (curr->left != nullptr) { 329 prev = curr; 330 curr = curr->left; 331 } 332 Tval = curr->val; 333 del_single(curr, prev); to emove 318 del_single(curr, prev); 319 return val; 320 } 321 // removes and returns the minimum value in the tree. 322 template 323 I BST::remove_min() { 324 if (is_empty()) 325 throw "Attempting to remove the min value from an empty tree"; 326 BSTNode+ curr = root; 327 BSTNode+ prev = nullptr; 328 while (curr->left != nullptr) { 329 prev = curr; 330 curr = curr->left; 331 } 332 I val = curr->val; 333 del_single(curr, prev); 334 return val; 335 } 336 // copy assignment 337 template 338 BST& BST:: operator=(const BST& other) 339 { 340 // Guard self assignment 341 if (this == &other) 342 return *this; 343 clear(); 344 copy_from (other.root); 345 return this; 346 }