Write and test the following methods for the BST $($Binary Search Tree$)$ class

Using the files supplied that contain some already$-$written BST class methods, add these

methods to the BST class. Make sure they all work in all supplied tests.

NOTE: Most of the methods can $($and should$)$ be done using recursion. Since the headers

for the methods do not easily support recursion $($due to the lack of parameter passing$),$ you

should consider writing a $($private$)$ helper method alongside several of the methods listed

below. The methods can then simply call the private recursive method with the necessary

argument$($s$)($such as a BSTNode$*$ pointer and$/$or a call$-$by$-$reference int value$)$ to perform a

proper recursion.

There are $10$ methods to be written and tested. Note: balancing of trees is NOT required!

void BST::preorderTraversal$()$ const

Side effect: cout to the screen the values of all the tree's nodes listed in preorder

void BST::inorderTraversal$()$ const

Side effect: cout to the screen the values of all the tree's nodes listed in inorder

void BST::postorderTraversal$()$ const

Side effect: cout to the screen the values of all the tree's nodes listed in postorder

int BST::countNodes$()$ const

Returns: An int value of the total number of nodes in the tree

int BST::countLeafs$()$ const

Returns: An int value of the total number of leafs in the tree

nt BST::countInterior$()$ const

Returns: An int value of the total number of interior nodes $($all non$-$leafs$)$ in the tree

int BST::treeHeight$()$ const

Returns: An int value of the height in the tree $($see "height definition" from our online text$)$

bool BST::deleteNode$($T el$)$

Input: A value of type T containing the value of the node to be deleted

Output: true if that value was found and the node deleted, false if value not found in tree

Side effect: Deletes the node containing that value $($and deallocates its memory$)$ from the

tree, using the Delete by Copying method. No rotations are necessary.

bool BST::leftRotation$($BSTNode& gr$,$ BSTNode& par, BSTNode& ch$)$

Expects: CALL BY REFERENCE of the Grandparent, Parent, and $($Right$)$ Child nodes

Returns: true if the rotation is successful, false if the rotation could not be performed

Side effect: Performs a BST Left Rotation of par $($promoting the child and demoting

the parent$),$ and updates all appropriate pointers. This method should also check that the

nodes have the correct parent$/$child relationship before attempting to rotate.

bool BST::rightRotation$($BSTNode& gr$,$ BSTNode& par, BSTNode& ch$)$

Expects: CALL BY REFERENCE of the Grandparent, Parent, and $($Left$)$ Child nodes

Returns: true if the rotation is successful, false if the rotation could not be performed

Side effect: Performs a BST Right Rotation of par $($promoting the child and demoting

the parent$),$ and updates all appropriate pointers. This method should also check that the

nodes have the correct parent$/$child relationship before attempting to rotate.