Implementing a Binary Search Tree in Java

Let us begin implementing a Binary Search Tree. It is a special version of a Tree in which each Tree node can contain only 0, 1, or 2 children (each node can have a left & right child node). In addition the value in each left child Tree node is less than the value of it’s parent Tree node and each right child Tree node’s value is greater than its parent. This allows for easy searching of the tree, hence the name Binary Search Tree.

First let’s declare our MyBinarySearchTree class:

public class MyBinarySearchTree<T extends Comparable<T>> {

}

The MyBinarySearchTree class is defined to have a Type of T. This means that the type of data held in the Tree is set during instantiation of a new MyBinarySearchTree. In addition the Type must extend the Comparable interface so that items can be compared (via the compareTo() function) to determine which items are greater, lesser, and equal.

We’ll need to define a TreeNode class for our MyBinarySearchTree class to hold the data as well as the Tree structure. In this class we’ll need three variables: data, left, and right. Data will hold the data associated with this Node. The left can potentially hold another TreeNode (or null if there is no Node). Remember that the left TreeNode must always be less than or equal to the current Node. The right can also potentially hold another TreeNode (or null if there is no Node). Similarly the right TreeNode must always be greater than the current Node.

The implementation of the TreeNode class is as follows:

    private class TreeNode<U extends Comparable<U>> {
        public TreeNode<U> left = null;
        public TreeNode<U> right = null;
        public U data = null;
        public TreeNode(U data) {
            this.data = data;
        }
    }

The TreeNode class is typed similarly to our MyBinarySearchTree class. Our MyBinarySearchTree class will need class level variables to hold the size of the tree as well as the root node of the tree.

private TreeNode<T> rootNode = null;
private int size = 0;

The constructor for the MyBinarySearchTree doesn’t actually need to do anything so we can leave it blank.

public MyBinarySearchTree() {

}

Now let us write a function to allow for inserting data into the BinarySearchTree. The function definition will look as follows:

public void insert(T data) {

}

Before starting to write our insert function it would be wise to think of the edge cases. Here there are two:

1. An empty tree (AKA the rootNode is null)
2. A non-empty tree (AKA the rootNode is not null)

Here’s how we will handle each case:

1. Create a new tree node and assign the root node to be the new node.
2. Create a new tree node. Traverse the tree to the position of the tree that the node should be at and add it there (IE add it to the left or right sub node of the correct parent node).

First declare a new tree node from the input data.

TreeNode<T> newNode = new TreeNode<T>(data);

Set the root node to be equal to the newly declared node if there is no root node (ie rootNode == null).

	if(rootNode == null) {
		rootNode = newNode;
	} else {
		// add handling for a non null root node here
	}

Declare a new tree node parentNode and set it to the rootNode. This is named parentNode as it will eventually end up being equal to the parent of the newNode. Start a while loop. This while loop will loop while true (AKA forever). When we find the correct place to add the newNode we will break out of the while loop.

		TreeNode<T> parentNode = rootNode;
		while(true) {
			// find the correct place to add the newNode here
		}

Next compare the data in the parentNode to the data in the newNode. If it is less than or equal to the parentNode then it’s place in the tree is down the left subtree of the parentNode. If the parentNode has no left subtree then we have found the correct place to add the newNode and we set the left TreeNode of the parentNode to the newNode and break out of the for loop. If the parentNode has a left subtree then we simply set the parentNode to be equal to the parentNode’s left TreeNode to traverse down the tree. Similarly if the data in the parent node is greater than the data then it’s place in the tree is down the right subtree of the parentNode. If the parentNode has no right subtree then we have found the correct place to add the newNode and we set the right TreeNode of the parentNode to the newNode and break out of the for loop. If the parentNode has a right subtree then we simply set the parentNode to be equal to the parentNode’s right TreeNode to traverse down the tree.

The code to implement this looks as follows:

			if(data.compareTo(parentNode.data) <= 0) {
				if(parentNode.left == null) {
					parentNode.left = newNode;
					break;
				}
				parentNode = parentNode.left;
			} else {
				if(parentNode.right == null) {
					parentNode.right = newNode;
					break;
				}
				parentNode = parentNode.right;
			}

Finally at the end of the insert function we need to increment the size variable by one as we have added another element to the tree.

size++;

The finished insert function is as follows:

public void insert(T data) {
	TreeNode<T> newNode = new TreeNode<T>(data);
	if(rootNode == null) {
		rootNode = newNode;
	} else {
		TreeNode<T> parentNode = rootNode;
		while(true) {
			if(data.compareTo(parentNode.data) <= 0) {
				if(parentNode.left == null) {
					parentNode.left = newNode;
					break;
				}
				parentNode = parentNode.left;
			} else {
				if(parentNode.right == null) {
					parentNode.right = newNode;
					break;
				}
				parentNode = parentNode.right;
			}
		}
	}
	size++;
}

Next let’s add a contains function to return whether or not a function contains a data value. The function definition is as follows:

public boolean contains(T data) {

}

Declare a TreeNode node and set it to the value of the rootNode.

TreeNode<T> node = rootNode;

Declare a while loop to traverse down the tree while node is not equal to null. If node ever becomes equal to null it means that our tree does not contain the data value. Return false at the end of the function.

	while(node != null) {
			// add code to transverse the tree here
	}
	return false;

While traversing the tree if the data in the current node is equal to the data being looked for return true as we have found the data in our tree. Otherwise if the data is less than the data in the node set node equal to its left subtree as that is the place that could potentially contain the data. Similarly if the data is greater than the data in the node set node equal to its right subtree as that is the place that could potentially contain the data.

		if(data.compareTo(node.data) == 0)
			return true;
		else if(data.compareTo(node.data) < 0)
			node = node.left;
		else
			node = node.right;

The finished contains function is as follows.

public boolean contains(T data) {
	TreeNode<T> node = rootNode;
	while(node != null) {
		if(data.compareTo(node.data) == 0)
			return true;
		else if(data.compareTo(node.data) < 0)
			node = node.left;
		else
			node = node.right;
	}
	return false;
}

The implementation of the MyBinarySearchTree will be continued in the following post: Implementing a Binary Search Tree in Java - Part Two.

Data Structures