Node Constructor

Set the data and parent to the passed$-$in values

Nodes always start out as leaf nodes

BST Constructor

Set all data members to reflect that no nodes are currently allocated

Push

Adds a value to the tree

Dynamically allocate a Node and place it in the correct position in the tree

Added nodes will always be leaf nodes

If there is already at least one node in the tree, you will need a temporary pointer to traverse down the tree to the node you want to insert below

Clear

Free up the memory for all dynamically allocated nodes

Use a post$-$order traversal and delete one node at a time

Set the root back to its default state

Destructor

Free up the memory for all dynamically allocated nodes $($There$$s a method that does this$)$

Contains

Checks to see if a value is present in the tree and returns true if found

Create a temporary pointer to traverse down the tree

FindNode $($Optional$)$

Checks to see if a value is present in the tree and returns the address if found

Create a temporary pointer to traverse down the tree

RemoveCase$0$

Removes a node from the tree that has no children

Can assume the node passed in is a leaf node

Three sub$-$cases

Root node

Is a left child

Is a right child

RemoveCase$1$

Removes a node from the tree that has one child

Can assume the node passed in has exactly one child

Six sub$-$cases

Root node with left child

Root node with right child

Left child that has a left child

Left child that has a right child

Right child that has a left child

Right child that has a right child

RemoveCase$2$

Removes a node from the tree that has both children

Can assume the node passed in has both children

This will ultimately lead to a Case$0$ or Case$1$ removal

Remove

Removes a node from the tree by calling the appropriate RemoveCase method

Find the address of the node to be removed $($There$$s potentially a method for this$)$

Check to see how many children that node has, and call the appropriate RemoveCase method

Return true, if something was removed

InOrder

Creates a space$-$delimited string that contains the values of the tree in ascending order

Start with the root and use the recursive InOrder method to build out the string one value at a time

Use std::tostring to convert the int into its string equivalent

Assignment Operator

Assigns all values to match those of the object passed in

Clean up existing memory before the deep copy $($There$$s a method that does this$)$

Deep copy the entire tree

Use the recursive Copy method to duplicate the tree with a pre$-$order traversal

Each recursive call to copy should create a single node by Pushing it

Copy Constructor

Assigns all values to match those of the object passed in

Deep copy the entire tree

Use the recursive Copy method to duplicate the tree with a pre$-$order traversal

Each recursive call to copy should create a single node by Pushing it