Binary Search Trees

If root == Null return NULL
Else set a temp pointer = root of the tree
Loop while (temp NOT null) AND (key not found)
	If search key == temp->key
		Search node found so set FOUND flag to true
	Else 
		If search key < temp->key
			temp = temp->left
		Else temp = temp->right
end Loop
If temp == NULL 
	return appropriate value to signal search failed
else
	do required action for found item

Set temp pointer = root,  set back pointer = NULL
Loop while (temp NOT= NULL)
	set back = temp
	If newNode->key < temp->key 
		set temp = temp->left
	else set temp = temp->right
end loop
Insert the newNode
	If back == NULL set root = newNode (first in tree)
	Else if newNode->key < back->key
		back->left = newNode
	Else
		back->right = newNode

If root is NULL return NULL (Case 1)
Set a temp pointer = root, set back pointer == NULL
Find position of node to be deleted
	Loop while (temp NOT=NULL) AND (search key != temp->key)
		back = temp
		if (search key < temp->key) set temp = temp->left
		else set temp = temp->right
	If (temp == NULL) search key was not found (Case 2)
		return
	Else if (temp==root) (deleting root node)
		set delNode = temp
		set delParent = NULL
	Else (deleting a node other than root)
		set delNode = temp
		set delParent = back

If delNode->right == NULL (Case 3 and/or 4: No children or 1 on left)
	if delParent == NULL (Deleting the root)
		set root = delNode->left  
		delete delNode
		return
	else  (see which side of delParent, delNode is on)
		if delParent->left == delNode
			set delParent->left = delNode->left
		else
			set delParent->right = delNode->left
		delete delNode
		return
Else if delNode->left == NULL (Case 5: Only 1 child and it is on right)
	if delParent == NULL (Deleting the root)
		set root = delNode->right  
		delete delNode
		return
	else  (see which side of delParent, delNode is on)
		if delParent->left == delNode
			set delParent->left = delNode->right
		else
			set delParent->right = delNode->right
		delete delNode
		return
Else (Case 6: Two children)
	Find replacement node, i.e. The one with the largest value in the left
	subtree, but less than the node to be deleted.  This will be the right-
	most node in the left subtree of the node to be deleted.
		Set temp = delNode->left
		Set back = delNode
		while temp->right != NULL
			back = temp
			temp = temp->right
	Copy replacement values from node pointed to by temp into node
		pointed to by delNode
	Remove the replacement node (a leaf) from the tree
		If back == delNode (the first node on the left had no right child)
			set back->left = temp->left
		Else set back->right = temp->left
		delete temp
		return

If root == Null return
Recursively call function with root->left
Do something with root
Recursively call function with root->right

// Public function to begin traversal by calling
//  the private function and passing in the root
//  which is also private.
void TreeClass::printTree()
{
    printAll(root); // Make call to private function
}

// Private function to perform in order traversal
//  and print all data in the tree
void TreeClass::printAll(TreeNode *rt)
{
    if(rt != NULL) // Base case
    {
        printAll(rt->left); // Recursive call to the left
        printOne(rt); // Print data in this node
        printAll(rt->right); // Recursive call to the right
    }
}

// Function to print all data in one node
void TreeClass::printOne(TreeNode *node)
{
    // Code to print all fields in the node
    //  is placed here.
}