Binary Search Tree Implementation in Java

We have already implemented a Binary Tree in Java a few weeks back, and this is the logical continuation of that. In this post, we’ll see how we can implement a Binary Search Tree (BST) in Java. This is very similar to binary tree, but there is one requirement that a binary tree has to fulfil to qualify as a binary search tree. And that requirement is that:

the values of all nodes to the left of a root node must be less than the value of the root node, and the values of all nodes to the right of a root node must be greater than the value of the root node. 

If a binary tree satisfies this requirement, it’ll become a binary search tree. So let’s see what that means code-wise.

Binary Search Tree

To understand the working of a BST and the code, we’ll need a reference tree, and that is shown in the image below.

As you can see from the sample BST shown above, values of all the nodes to the left of every node is less than the value of the root node, and the values of all the nodes to the right of every node is greater than the root node. Whenever a node is inserted or deleted from this tree, we have to make sure that we maintain this distribution of values. Right then, let’s get to the code.

Adding a node to a binary search tree

Adding a node to a BST is pretty much similar to adding a node in binary tree. But in a BST, you have a couple of extra steps. What I mean here is that when you’re adding a new node to a BST, you can’t just add it a random location. You need to make sure that you’re still maintaining all the properties of a BST. And that means you need to find the node under which you can add the new node in such a way that the values are still on the correct side of the node. Let’s take an example to understand better.

But before that, there are three checks you need to make while adding a new node to a BST:

• Is the root node null? (The BST is empty)
• Is the value of the root node less than the value of the new node?
• Is the value of the root node greater than the value of the new node?

We’ll look at each of these cases separately.

Is the root node null?

This is the first check we need to do while adding a new node to a BST. If this condition turns out to be true, that means the BST is still empty, and you need to instantiate the BST. So you just assign the new node to the root node. The node you’re trying to add becomes the root node. The code for this is pretty straight forward:

if (rootNode == null) {
    rootNode = node;
}

I’m not going to explain this more, because frankly, there’s nothing to explain.

Is the value of the root node less than the value of the new node?

If this is the case, we know that the new node has to go to the right sub-tree of the root node. So we’ll call the same method recursively until the right sub-tree of the node is null. This means that we have reached the deepest point of the BST on the right before the BST property is false. At this point, we’ll set the right sub-tree of the current node to the new node. Let’s see the code to understand this better:

if (rootNode.getValue() < node.getValue()) {
    if (rootNode.getRight() != null) {
    	// Calling the same method.
        add(rootNode.getRight(), node);
    } else {
        rootNode.setRight(node);
    }
}

As you can see, there is a recursive call to the same method until the right sub-tree is null. If the right sub-tree is null, we’ll replace that null with the new node. This way, the property of the BST is maintained without any issue. And the next case is quite the opposite of this.

Is the value of the root node greater than the value of the new node?

Similar to the previous case, we’ll have to take care of the left sub-tree as well. This will happen when the value of the root node is greater than the value of the node we’re trying to add. So we’ll call the same add() method recursively until we reach the point where the left sub-tree is null. Let’s see the code:

if (rootNode.getValue() > node.getValue()) {
    if (rootNode.getLeft() != null) {
    	// Calling the same method.
        add(rootNode.getLeft(), node);
    } else {
        rootNode.setLeft(node);
    }
}

As you can see, this is very similar to the previous case, the only difference is that we’re moving deep into the left sub-tree instead of the right sub-tree in the previous case.

All these three cases have to be taken care of in the same method. So when we combine all the three code snippets into one method, that method looks like the following:

public void add(Node rootNode, Node node) {
    if (rootNode == null) {
        rootNode = node;
    } else if (rootNode.getValue() < node.getValue()) {
        if (rootNode.getRight() != null) {
            add(rootNode.getRight(), node);
        } else {
            rootNode.setRight(node);
        }
    } else if (rootNode.getValue() > node.getValue()) {
        if (rootNode.getLeft() != null) {
            add(rootNode.getLeft(), node);
        } else {
            rootNode.setLeft(node);
        }
    }
}

So, that concludes the add() method. Now, let’s see how to handle the delete function.

Deleting a node from a binary search tree

Deleting a node is not quite straight forward, similar to adding a node. We need to make sure that the balance of the tree is still maintained when we delete a node. And there are several cases to take care of here as well. Let’s have a look at them one by one.

The node we’re trying to delete doesn’t exist

Well, there’s nothing much we can do. We’ll just log a message, maybe, and move on. If you’re interested to see how the code for this looks like, here you go:

if (nodeToDelete == null) {
    // There's no node with the given value.
    System.out.println("Node not found!");
}

The node we’re trying to delete is a leaf node

A leaf node is a node which doesn’t have any children. So in this case, the node we’re trying to delete doesn’t have anything on its left or right. This a pretty straight forward case as well. When this is the case, first, we’ll get the parent node of this node. Then, we’ll check if the node we are deleting is on the right of the parent node, or on the left. Once we know this, we’ll just make the reference on the corresponding side null. This way, the reference to the node will be lost and the node will be garbage collected in the next run. Let’s see the code for this, and hope it’ll be a bit more clear to understand.

if (nodeToDelete.getLeft() == null && nodeToDelete.getRight() == null) {
    // Node has no children, so just remove reference of its parent.
    Node parentNode = getParentNode(rootNode, valueToSearch);
    if (parentNode != null) {
        if (parentNode.getRight().getValue() == valueToSearch) {
            parentNode.setRight(null);
        } else if (parentNode.getLeft().getValue() == valueToSearch) {
            parentNode.setLeft(null);
        }
    }
}

The node we’re trying to delete has only right or left sub-tree

These are actually two different cases, but they’re very similar. So I’m clubbing them to make it easy. When the node we’re trying to delete has only the left sub-tree or the right sub-tree, it’s very easy for us to delete the node. But we have to take care that the sub-tree of the node is not lost. To make sure of this, we’ll just move the sub-tree of the node one level up. So the parent of the node we’re trying to delete will become the parent of the sub-tree of the node being deleted. I hope I didn’t make it more complicated to understand. Take a look at the code and see if you can understand:

if (nodeToDelete.getLeft() == null) {
    // Only right children is present. So link parent node's right to current node's right.
    Node parentNode = getParentNode(rootNode, valueToSearch);
    if (parentNode != null) {
        parentNode.setRight(nodeToDelete.getRight());
    }
} else if (nodeToDelete.getRight() == null) {
    // Only left children is present. So link parent node's left to current node's left.
    Node parentNode = getParentNode(rootNode, valueToSearch);
    if (parentNode != null) {
        parentNode.setLeft(nodeToDelete.getRight());
    }
}

The node we’re trying to delete has both left and right sub-tree

This is possibly the most important check while deleting a node in a BST. In the situation where the node we’re trying to delete has both the left and right sub-tree, we have find the successor of the node. What is a successor? Well, a successor node is the node with the lowest value on the right sub-tree of the node we’re trying to delete.

So for example, assume we’re deleting the node with the value 10 in our example BST pictured at the beginning of this post. The successor of this node is the node with the lowest value on the right sub-tree of the node 10. And that’s the node with the value 12.

Once we find that node, we’ll just replace the node we’re trying to delete with this successor node. This way, the balance of the BST is still maintained. So the children of the node with value 10 will become the children of the node with value 12, which will be the new root node. Now, let’s look at the code to make more sense of it:

// Both right and left children are present. So need to get the successor of the node.
Node parentNode = getParentNode(rootNode, valueToSearch);
Node successorNode = getSuccessorNode(nodeToDelete.getRight());

if (parentNode.getRight().getValue() == valueToSearch) {
    parentNode.setRight(successorNode);
    delete(rootNode, successorNode.getValue());
} else if (parentNode.getLeft().getValue() == valueToSearch) {
    parentNode.setLeft(successorNode);
    delete(rootNode, successorNode.getValue());
}

There are two more functions here, getParentNode() and getSuccessorNode(). Let’s see what these functions look like:

public Node getParentNode(Node rootNode, int valueToSearch) {
    if (rootNode == null) {
        return null;
    } else if (rootNode.getValue() == valueToSearch) {
        return rootNode;
    } else if (rootNode.getValue() < valueToSearch) {
        if (rootNode.getRight() != null) {
            if (rootNode.getRight().getValue() == valueToSearch) {
                return rootNode.getRight();
            } else {
                return getParentNode(rootNode.getRight(), valueToSearch);
            }
        } else {
            return null;
        }
    } else if (rootNode.getValue() > valueToSearch) {
        if (rootNode.getLeft() != null) {
            if (rootNode.getLeft().getValue() == valueToSearch) {
                return rootNode.getLeft();
            } else {
                return getParentNode(rootNode.getLeft(), valueToSearch);
            }
        } else {
            return null;
        }
    }

    return null;
}

private Node getSuccessorNode(Node node) {
    if (node.getLeft() == null) {
        return node;
    } else {
        return getSuccessorNode(node.getLeft());
    }
}

I’ll not be explaining these two functions, because I think they’re pretty self explanatory. But those two functions are necessary for the delete operation. If this is tricky to understand or if you think I’ve not done a good job explaining it, please leave a comment below or connect with me, and I’ll be happy to explain it better.

Anyway, once we have these functions in place, we’re pretty much done with the code for creating a binary search tree, and for performing all the functions of a BST. Now, let’s see how we can construct the tree I’ve shown in the image earlier in this post.

Constructing a Binary Search Tree

The code for constructing the BST shown in the image earlier in this post is as follows:

BinarySearchTree binarySearchTree = new BinarySearchTree(new Node(10));
binarySearchTree.add(binarySearchTree.getRootNode(), new Node(15));
binarySearchTree.add(binarySearchTree.getRootNode(), new Node(7));
binarySearchTree.add(binarySearchTree.getRootNode(), new Node(5));
binarySearchTree.add(binarySearchTree.getRootNode(), new Node(8));
binarySearchTree.add(binarySearchTree.getRootNode(), new Node(12));
binarySearchTree.add(binarySearchTree.getRootNode(), new Node(18));

Because we have written the code to find the right place to insert a new node, we don’t have to worry about providing the correct root node for each add() operation. We just provide the root node of the BST, and it will be inserted at the right place. We can verify this further by looking at the outputs of the traversal operations. Let’s see that in the next section.

In-order traversal for a BST

The code for all the traversals in a BST in the exact same as a binary tree. But nonetheless, I’m going to reproduce that code here again:

public static String traverseInOrder(Node node, StringBuilder stringBuilder) {

    if (stringBuilder == null) {
        stringBuilder = new StringBuilder();
    }

    if (node.getLeft() != null) {
        traverseInOrder(node.getLeft(), stringBuilder);
    }

    stringBuilder.append(node.getValue()).append(" ");

    if (node.getRight() != null) {
        traverseInOrder(node.getRight(), stringBuilder);
    }

    return stringBuilder.toString();
}

When you call this function on the BST that we constructed earlier, you should see the output like this:

5 7 8 10 12 15 18 

Pre-order traversal for a BST

The code for pre-order traversal for a BST is as follows:

public static String traversePreOrder(Node node, StringBuilder stringBuilder) {

	if (stringBuilder == null) {
	    stringBuilder = new StringBuilder();
	}

	stringBuilder.append(node.getValue()).append(" ");

	if (node.getLeft() != null) {
	    traversePreOrder(node.getLeft(), stringBuilder);
	}

	if (node.getRight() != null) {
	    traversePreOrder(node.getRight(), stringBuilder);
	}

	return stringBuilder.toString();
}

The output of this is follows:

10 7 5 8 15 12 18 

Post-order traversal for a BST

The code for post-order traversal for a BST is as follows:

public static String traversePostOrder(Node node, StringBuilder stringBuilder) {

    if (stringBuilder == null) {
        stringBuilder = new StringBuilder();
    }

    if (node.getLeft() != null) {
        traversePostOrder(node.getLeft(), stringBuilder);
    }

    if (node.getRight() != null) {
        traversePostOrder(node.getRight(), stringBuilder);
    }

    stringBuilder.append(node.getValue()).append(" ");

    return stringBuilder.toString();
}

The output of the code is shown below:

5 8 7 12 18 15 10 

I know this has been a very long post. But there is so much that has to be discussed in a binary search tree. Let me know in the comments below if you want me to split such long posts into multiple parts. Anyway, if you want to take a look at the project directly, as usual, you can find it in my Github repo.

And if you like what you see here, or on my Medium blog, and would like to see more of such helpful technical posts in the future, consider supporting me on Patreon and Github.