c++

1) Define a header file named BST.h. In this header file, declare your BST class. /* ** header file BST.h */ class BST { private: struct TreeNode { int val; TreeNode* left; TreeNode* right; }; TreeNode* root; // private function declarations here .... public: // public function declarations here ... }

2). Define a cpp file named BST.cpp to implement the functions you declared in your header file. /* ** BST.cpp */ #include \"BST.h\"

// functions implementations

3.Define another cpp file named assignment3.cpp to provide a user interface to test your implementation. #include \"BST.h\" ... int main(){ while (//design a mechanism to test your implementation continuously until users input is 0) { cout cout } }

A. Insert a node to BST You will need to ensure there are no duplicated in your insert function (i.e., the tree should refuse to insert a duplicate key). B.Search a value from BST If the user input value is one of the keys stored in your BST, return 1; otherwise, return -1. C.Find the predecessor for a given value Input an existing value stored in your tree, and return the value stored in its predecessor node. You do not need to consider the situation when the input value is not stored in your BST. Only input the values already stored in your BST. D.Find the successor for a given node Input an existing value stored in your tree, and return the value stored in its successor node. You do not need to consider the situation when the input value is not stored in your BST. Only input the values already stored in your BST

E.Find the height of the tree Return the height of your BST. The return value should be an integer. F.Number of nodes in your tree Return the number of total nodes in your BST. The return value should be an integer. G.Delete a leaf node based on the value Delete a leaf node based on the value given by the user. After deleting the node, your BST should be reconstructed. You do not need to consider the situation when the input value is not stored in your BST or the input value is not a value in leaf nodes. H.Traverse the tree INORDER I.Traverse the tree PREORDER J.Traverse the tree POSTORDER K.Balance check Input the root note of this tree. If this BST is balanced, return 1; otherwise, return -1. L.Destroy the tree Return nullptr after the tree is destroyed successfully.