Implementing a Binary Search Tree in Java - Part Two

Let’s get back to implementing our MyBinarySearchTree class. We need a way to remove a value from the tree. Bear with me here as doing this will become quite complicated as we will have to make sure to preserve the properties of binary search when removing values.

Before starting to write our remove function it would be wise to think of the edge cases. Here there are five(!):

1. An empty tree (AKA the rootNode is null)
2. The data to remove is in the rootNode and the rootNode has no children
3. The data to remove is not in the rootNode
4. The data to remove is in the rootNode and the rootNode has children
5. The data to remove is not in the tree

Here’s how we will handle each case:

1. Return false as there is no data to remove.
2. Set the size to zero and rootNode to null. Return true.
3. Traverse down the tree while keeping track of the current node as well as it’s parent. When the node to remove is found remove it from the parent node and replace it with the largest node on the left subtree of the node or the smallest node on the right subtree of the node. If the node has no children then set it to null. Make sure to remove the child node from it’s parent node. This will ensure that the binary search property is maintained in the tree.
4. Similarly traverse the tree. Instead of replacing the node in its parent simply set the correct child node (the largest node on the left subtree or smallest node on the right subtree) to be the rootNode. Set the new rootNodes left & right subtrees to be the same as the rootNodes.
5. Traverse down the tree looking for the inputted value. If it is not found, return false.

The remove function definition is as follows:

public boolean remove(T data) {
	
}

First off return false if the tree is empty.

  	if(rootNode == null)
  		return false;

If the data to remove is in the rootNode and the rootNode has no children then simply set the rootNode to null and the size to zero before returning true.

  	if(data.compareTo(rootNode.data) == 0 && rootNode.left == null && rootNode.right == null) {
  		size = 0;
  		rootNode = null;
  		return true;
  	}

Declare nodes to hold the TreeNode that we will be deleting (accordingly named toDelete) and the parent TreeNode of the TreeNode to be deleted (accordingly named parentNode). toDelete will initially be set to the rootNode and parentNode will be initially null (as the rootNode has no parentNode).

  	TreeNode<T> parentNode = null;
  	TreeNode<T> toDelete = rootNode;

Recurse down through the tree looking for the node we need to delete. If the current node is < the node to delete then the node to delete is in the left subtree (set toDelete equal to it’s left node). If the current node is > then the node to delete is in the right subtree (set to delete to its right node). If it is equal then we have found the node to delete. Make sure to update the value of the parentNode while recursing through the tree so that it is equal to the parent of the toDelete node. If we make it through the tree without finding the node to delete (ie. toDelete becomes equal to null) then return false.

	while(toDelete != null) {
		if(data.compareTo(toDelete.data) == 0) {
			//this is where we remove the node
		} else if(data.compareTo(toDelete.data) < 0) {
			parentNode = toDelete;
			toDelete = toDelete.left;
		} else {
			parentNode = toDelete;
			toDelete = toDelete.right;
		}
	}

Now let’s begin writing to code to actually delete the toDelete node after it is found. Let’s start off by trying to find the maximum node in the left subtree as well as it’s parent. We’ll for now pretend we have a function to do this called getMaxNodeAndParent() (we will write this function later on). Let’s also declare the nodes toMove and toMoveParent both which we’ll set equal to null for now. toMove will be later set equal the node to replace toDelete with and toMoveParent will be set equal to toMove’s parent node.

			Pair<TreeNode<T>, TreeNode<T>> pair = getMaxNodeAndParent(toDelete, toDelete.left);
			TreeNode<T> toMove = null;
			TreeNode<T> toMoveParent = null;

If there’s a pair found (ie pair != null) then we’ll set the toMoveParent and toMove appropriately to the pair’s key & value. We will then remove the toMove node from it’s parent by setting the toMoveParent nodes left or right node to the toMove node’s left node (depending on which side of the toMoveParent node it was on). This effectively unlinks the toMove node from it’s parent (ie removing it from the tree). By setting the position it was in in toMoveParent with the toMove node’s left subtree we make sure that the nodes underneath the toMove node are kept in the tree. The node in toMove.right will be equal to null by definition of a binary search tree since there are no nodes greater then toMove that are in the toDelete.left node’s subtree. We will later put the toMove node back into the tree in place of the toDelete node.

			if(pair != null) {
				toMoveParent = pair.getKey();
				toMove = pair.getValue();
				if(toMoveParent.left == toMove)
					toMoveParent.left = toMove.left;
				else
					toMoveParent.right = toMove.left;
			}

If there is not a pair found then we’ll look for the minimum node in the right subtree as well as it’s parent. We’ll also pretend we have a function to do this called getMinNodeAndParent() (we will write this function later on). If this is pair is non null we will then similarly set the toMove & toMoveParent nodes and remove the toMove node from the toMoveParent as done in the previous step.

			} else {
				pair = getMinNodeAndParent(toDelete, toDelete.right);
				if(pair != null) {
					toMoveParent = pair.getKey();
					toMove = pair.getValue();
					if(toMoveParent.left == toMove)
						toMoveParent.left = toMove.right;
					else
						toMoveParent.right = toMove.right;
				}
			}

Next if we’ve found a node toMove to move into toDelete’s position (ie toMove != null) we set toMove’s left and right nodes to toDelete’s left and right nodes to preserve the tree structure.

			if(toMove != null) {
				toMove.left = toDelete.left;
				toMove.right = toDelete.right;
			}

If toMove is equal to null we don’t have to do anything as that means that toDelete has no children to preserve.

Next if the parentNode is not equal to null (ie the toDelete node is not the root node) we need to replace the toDelete node (which will be in the parents left or right node) with the toMove node in either parentNode.left or parentNode.right (depending on where it is) to completely remove the toDelete node. If the parent node is equal to null (ie the toDelete node is the rootNode) we simply set the rootNode to be equal to the toMove node.

			if(parentNode != null)
				if(parentNode.left == toDelete)
					parentNode.left = toMove;
				else
					parentNode.right = toMove;
			else
				rootNode = toMove;

Finally to complete the function we decrement the size variable by one and return true as we have removed the value from the tree.

			size--;
			return true;

The finished remove() function is as follows:

public boolean remove(T data) {
	if(rootNode == null)
		return false;
	if(data.compareTo(rootNode.data) == 0 && rootNode.left == null && rootNode.right == null) {
		size = 0;
		rootNode = null;
		return true;
	}
	TreeNode<T> parentNode = null;
	TreeNode<T> toDelete = rootNode;
	while(toDelete != null) {
		if(data.compareTo(toDelete.data) == 0) {
			//this is where we remove the node
			Pair<TreeNode<T>, TreeNode<T>> pair = getMaxNodeAndParent(toDelete, toDelete.left);
			TreeNode<T> toMove = null;
			TreeNode<T> toMoveParent = null;
			if(pair != null) {
				toMoveParent = pair.getKey();
				toMove = pair.getValue();
				if(toMoveParent.left == toMove)
					toMoveParent.left = toMove.left;
				else
					toMoveParent.right = toMove.left;
			} else {
				pair = getMinNodeAndParent(toDelete, toDelete.right);
				if(pair != null) {
					toMoveParent = pair.getKey();
					toMove = pair.getValue();
					if(toMoveParent.left == toMove)
						toMoveParent.left = toMove.right;
					else
						toMoveParent.right = toMove.right;
				}
			}
			if(toMove != null) {
				toMove.left = toDelete.left;
				toMove.right = toDelete.right;
			}
			if(parentNode != null)
				if(parentNode.left == toDelete)
					parentNode.left = toMove;
				else
					parentNode.right = toMove;
			else
				rootNode = toMove;
			size--;
			return true;
		} else if(data.compareTo(toDelete.data) < 0) {
			parentNode = toDelete;
			toDelete = toDelete.left;
		} else {
			parentNode = toDelete;
			toDelete = toDelete.right;
		}
	}
	return false;
}

We will continue our MyBinarySearchTree in the following post: Implementing a Binary Search Tree in Java - Part Three.

Data Structures