BST.h

#ifndef __BST_H #define __BST_H #include  #include  using namespace std; /* * Data structure for a single tree node */ template  struct Node { public: T value; Node* left; Node* right; Node(T val) { this->value = val; this->left = nullptr; this->right = nullptr; } ~Node() { this->value = 0; this->left = nullptr; this->right = nullptr; } }; /* * Binary Search Tree (BST) class implementation */ template  class BST { protected: Node* _root; // Root of the tree nodes /* Add new T val to the tree */ void addHelper(Node* root, T val) { if (root->value > val) { if (!root->left) { root->left = new Node(val); } else { addHelper(root->left, val); } } else { if (!root->right) { root->right = new Node(val); } else { addHelper(root->right, val); } } } /* Print tree out in inorder (A + B) */ void printInOrderHelper(Node* root) { if (!root) return; printInOrderHelper(root->left); cout value right); } /* Return number of nodes in tree */ int nodesCountHelper(Node* root) { if (!root) { return 0; } else { return 1 + nodesCountHelper(root->left) + nodesCountHelper(root->right); } } /* Return height of tree (root == nullptr -> 0) */ int heightHelper(Node* root) { if (!root) { return -1; } else { return 1 + max(heightHelper(root->left), heightHelper(root->right)); } } /* Delete a given  value from tree */ bool deleteValueHelper(Node* parent, Node* current, T value) { if (!current) return false; if (current->value == value) { if (current->left == nullptr || current->right == nullptr) { Node* temp = current->left; if (current->right) temp = current->right; if (parent) { if (parent->left == current) { parent->left = temp; } else { parent->right = temp; } } else { this->_root = temp; } } else { Node* validSubs = current->right; while (validSubs->left) { validSubs = validSubs->left; } T temp = current->value; current->value = validSubs->value; validSubs->value = temp; return deleteValueHelper(current, current->right, temp); } delete current; return true; } return deleteValueHelper(current, current->left, value) || deleteValueHelper(current, current->right, value); } /********************************* PUBLIC API *****************************/ public: BST() : _root(nullptr) { } // Basic initialization constructor /** * Destructor - Needs to free *all* nodes in the tree * TODO: Implement Destructor */ ~BST() { cout _root) { this->addHelper(this->_root, val); } else { this->_root = new Node(val); } } void print() { printInOrderHelper(this->_root); } /** * Print the nodes level by level, starting from the root * TODO: Implement printLevelOrder */ void printLevelOrder() { cout _root); } int height() { return heightHelper(this->_root); } /** * Print the maximum path in this tree * TODO: Implement printMaxPath */ void printMaxPath() { cout deleteValueHelper(nullptr, this->_root, value); } /** * Find if the BST contains the value * TODO: Implement contains */ bool contains(T value) { cout ::min(); } }; #endif 

main.cpp

#include "BST.h" int main() { BST *bst = new BST(); bst->add(11); bst->add(1); bst->add(6); bst->add(-1); bst->add(-10); bst->add(100); bst->print(); coutprintLevelOrder(); cout contains(100) contains(9) nodesCount(); coutheight(); coutprintMaxPath(); coutdeleteValue(11); coutprint(); coutprintLevelOrder(); coutnodesCount(); cout  In this micro-assignment, you will be implementing some missing code for a class BST template provided. You must work within your Linux environment. Please use the project given on Canvas. Specifically, you will need to implement code for the following 4 functions in BST.h and make sure all existing test cases in main() have the correct outputs. The only file you need to change is BST.h. (20 pts)-BST destructor (20 pts) contains (25 pts) printLevelOrder (25 pts) printMaxPath Other requirements: (5 pts) Correctly use GitHub and GitHub action. The given project already has a correct cmake.yml. Don't mess up. (5 pts) Correctly use cmake. The given project already has a correct CMakeLists.txt. Don't mess up. 1 Currently, the output of the test cases in main() is -10 -1 1 6 11 100 TODO: Implement printLevelOrder 100 in BST? true (1) or false (): TODO: Implement contains 9 in BST? true (1) or false (): TODO: Implement contains 1 Nodes count: 6 Height: 3 Max path: TODO: Implement printMaxPath After 11 removed: -10 -1 1 6 100 TODO: Implement printLevelOrder Nodes count: 5 TODO: Implement Destructor The correct output of the test cases in main() should be -10 -1 1 6 11 100 11 1 100 -16 -10 100 in BST? true (1) or false (): 1 9 in BST? true (1) or false (O): 0 Nodes count: 6 Height: 3 Max path: 11 1 -1 -10 After 11 removed: -10 -1 1 6 100 100 1 -16 -10 Nodes count: 5