Draw all the possible Binary Search Trees that contain four nodes with values 1, 2, 3, and 4. Ensure that each tree meets the criteria for a Binary Search Tree.
You are given a BST class template which supports a number of BST functions. You are to add BST functions as follows. For the functions provided in the BST class, you can assume these functions are correctly implemented. That is, a constructed Binary Search tree meets all the Binary Search Tree criteria. You can assume there are no duplicate entries in the Binary Search Tree. You can use any function that is provided in the BST class. You cannot change any function defintions. There are five functions to code in the BST.h file which are found at the bottom of the file. There are 19 testcases to pass. The results of the testcases are captured in the BST-results.txt file located in the working directory. The four files provided will initially compile together. The functions to implement are as follows:
1) countNodesAux(subtreeRoot) private member function. The function countNodes() is public member function of class BST that returns the total number of nodes in the tree. If the tree is empty, it returns zero. countNodes() calls unsigned countNodesAux(subtreeRoot). There is no extra coding needed for countNodes(). The countNodesAux(subtreeRoot) private member function is a recursive function that needs to be coded. This function returns the total number of nodes in the tree.
2) indexSearch(item) is a non-recursive public member function of class BST. This function returns the node index of a particular node in the tree. If the tree is empty OR the item is not in the tree, then a -1 is returned. It is highly recommended that you use the code for the search() algorithm already provided by the BST class as the basis for this implementation. The node index is the mapping of the nodes to an array starting with the root node at index 0. The second level of the tree contains index numbers 1 through 2 moving from left to right, the 3rd level of the tree contains index numbers 3 through 6, and so on. Therefore, if there were 3 nodes in the tree all on the extreme right side, the index of the last node is 6.
3) copyAux(BinNodePointer treeToCopy). The copy constructor is implemented by calling the recursive function copyAux(BinNodePointer treeToCopy). copyAux is a recursive private member function that needs to be implemented. The implementation will copy the nodes from treeToCopy to the current object at myRoot in the exact tree order. The new tree that is created will need to have nodes allocated from memory. You can assume that treeToCopy is a Binary Search Tree. Hint: review the six traversal patterns to find the appropriate one for this function.
4) destructAux(BinNodePointer subtreeRoot) The destructor is implemented by calling the recursive function destructAux(BinNodePointer subtreeRoot). destructAux is a recursive private member function that needs to be implemented. All nodes of the tree need to be deallocated. Hint: review the six traversal patterns to find the appropriate one for this function.
5) The assignment operator needs to be implemented and needs to use the copyAux() and destructAux() to accomplish its functionality. Fully implement the assignment operator using opyAux() and destructAux().