Data Members:

struct Node $\{$

Type data;

Node$*$ left, $*$right;

Node$*$ parent;

$//$node Constructor goes here if implemented correctly

$\}$

BST:

mRoot $-$ Pointer to the root $($top$)$ node

Methods:

Node Constructor

Node$($const Type& $\_$data, Node$*\_$parent $=$ nullptr$)$ : data$(\_$data$),$ parent$(\_$parent$)\{$

left $=$ right $=$ nullptr;

$\}$

BST Constructor

BST$()\{$

mRoot $=$ nullptr;

$\}$

Push

void Push$($const Type& $\_$val$)\{$

$$ Node$*$ newNode $=$ new Node$(\_$val$)$;

$$ if $($mRoot $==$ nullptr$)\{$

$$ mRoot $=$ newNode;

$$ return;

$\}$

$$ Node$*$ temp $=$ mRoot;

$$ while $($temp $!=$ nullptr$)\{$

$$ if $(\_$val $<*$temp$)\{$

$$ if $($temp$->$left $==$ nullptr$)\{$

$$ temp$->$left $=$ newNode;

$$ break;

$\}$

$$ temp $=$ temp$->$left;

$\}$ else $\{$

$$ if $($temp$->$right $==$ nullptr$)\{$

$$ temp$->$right $=$ newNode;

$$ break;

$\}$

$$ temp $=$ temp$->$right;

$\}$

$\}$

$\}$

Clear

void Clear$()\{$

$$ Clear$($mRoot$)$;

$$ mRoot $=$ nullptr;

$\}$

$//$Recursive helper method for use with Clear$()$

void Clear$($Node$*\_$curr$)\{$

$$ if $(\_$curr $==$ nullptr$)\{$

$$ return;

$\}$

$$ Clear$(\_$curr$->$left$)$;

$$ Clear$(\_$curr$->$right$)$;

$$ delete $\_$curr;

$\}$

Destructor

~BST$()\{$

Clear$()$;

$\}$

Contains

bool Contains$($const Type& $\_$val$)\{$

Node$*$ temp $=$ mRoot;

$$ while $($temp $!=$ nullptr$)\{$

$$ if $(\_$val $<$ temp$->$data$)\{$

$$ temp $=$ temp$->$left;

$\}$ else if $(\_$val $>$ temp$->$data$)\{$

$$ temp $=$ temp$->$right;

$\}$ else $\{$

$$ return true; $//$ value found

$\}$

$\}$

$$ return false; $//$ value not found

$\}$

FindNode $($Optional$)$

Node$*$ FindNode$($const Type& $\_$val$)\{$

$$ 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$

void RemoveCase$0($Node$*\_$node$)\{$

$$ Removes a node from the tree that has no children

$$ o Can assume the node passed in is a leaf node

$$ Three sub$-$cases

$$ o Root nodeo Is a left child

$$ o Is a right child

$\}$

RemoveCase$1$

void RemoveCase$1($Node$*\_$node$)\{$

$$ Removes a node from the tree that has one child

$$ o Can assume the node passed in has exactly one child

$$ Six sub$-$cases

$$ o Root node with left child

$$ o Root node with right child

$$ o Left child that has a left child

$$ o Left child that has a right child

$$ o Right child that has a left child

$$ o Right child that has a right child

$\}$

RemoveCase$2$

void RemoveCase$2($Node$*\_$node$)\{$

$$ Removes a node from the tree that has both children

$$ o Can assume the node passed in has both children

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

$\}$

Remove

bool Remove$($const Type& $\_$val$)\{$

$$ 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

std::string 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

$\}$

$//$Recursive helper method to help with InOrder

void InOrder$($Node$*\_$curr, std::string& $\_$str$)\{$

$//$Implement this method

$\}$

Assignment Operator

BST& operator$=($const BST& $\_$assign$)\{$

$$ 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

$$ o 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

BST$($const BST& $\_$copy$)\{$

$$ Assigns all values to match those of the object passed in

$$ Deep copy the entire tree

$$ o 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

$$ Remember that data members are not automatically initialized in C$++$

$\}$

$//$Recursive helper method for use with rule of $3$

void Copy$($const Node$*\_$curr$)\{$

$//$Implement this method

$\}$

Extra instructions for what some methods should do

Contains should check found and not found

RemoveCase$0$ should check root, left, right,

RemoveCase$1$ should check root$-$left, root$-$right, left$-$left, left$-$right, right$-$left, right$-$right

RemoveCase$2$ case$0$

RemoveCase$2$ case$1$

Check Remove not found

Some of these I have completed, I$\text{'}$m just a little confused about the otherss and was looking for clearer instructions on how to implement these?