# Binary Search Tree – Java Implementation with tests

Trees are fundamental data structures in computer science, and in this article we’ll explore the Binary Search Tree.

Before we dive into our binary search tree java implementation, let’s get a clear understanding of what a tree is, and when it is used.

As mentioned, trees are heavy used in the world of computer science. Some of the applications of the tree data structure is:

• Files in operating systems are almost always stored in trees, or data structures similar to a tree.
• Trees are often used when designing compilers.
• Application where text processing is used.
• Search algorithms often depend on trees.

## What is a Binary Search Tree?

Let’s start off by explaining what a general tree is. We’ll ignore the “binary search” to begin with.

The tree data structure can easily be understood if you visualize a traditional family tree, where you have parents and children.
Between the entities (nodes) in the family tree, there are relationships.

Now, let’s disregard the family tree, and focus on the actual tree data structure.

A tree data structure is composed of two things: nodes, and edges that connect the nodes.

The properties of a tree is as follows:

• One node is the “master-parent”, known as the root node. All the other nodes are inheritors of the root node.
• Every node is connected to another node by exactly one edge.
• Each and every node has a unique path back up to the root node.

The picture above is an example of a tree. Note that this is NOT a Binary Search Tree.
The node at the top, node A, is the root. All other nodes are inheritors of this node.
Nodes below the root node, are connected through lines. These lines are the edges that connect the nodes.

Now, how does the Binary Search Tree differ from a regular tree?

• A node can only have two children, thus binary.
• The left subtree of a node can only contain nodes which are less than the parent node’s key.
• The right subtree of a node can only contain nodes which are more than the parent node’s key.
• The left and right subtree each must also be a binary search tree.
• There can’t be any duplicate nodes.

The picture above is a Binary Search Tree.
The tree’s root is the node with key 4. All nodes to the left of root are less than 4, and all nodes to the right are more than 4.

## Binary Search Tree implementation in Java

Note that we’ll also write tests for our Binary Search Tree, using JUnit.

### The Node Class

A binary search tree consists of nodes, where each node can have a maximum of two children. Let’s implement our Node class.

### The BinarySearchTree Class

Let’s implement the BinarySearchTree.java, one operation at a time.
Remember that we’ll be implementing three common operations for a binary search tree – search, insert and delete.

We start off by creating a skeleton for the BinarySearchTree class.

As always, tests are written!

Now that we’ve made the class skeleton, and assured ourselves that it’s working as expected, we can implement the operations.

### Insert Operation

We want the following behavior for our insert operation:

• We must first find the correct place to insert the node.
• Start traversing the BST from root.
• Compare root.value with the value passed to the method, the value X.
• If root.value is greater than X, go to the left sub tree.
• If root.value is less than X, go to the right sub tree.
• If we reach a null value, we have found the correct place to insert a new node.

### Find Operation

The find (search) operation is a simple operation to perform, and very similar to the insert operation. It runs in O(logN).
NB! If you are unfamiliar with Big-Oh notation, check out Introduction to Algorithm Analysis.

For our find operation, we want the following behavior:

• Start from the root node and compare root.value with the value passed into the method, the value X.
• If root.value is greater than X, we need to go to the left sub tree.
• If root.value is less than X, we need to go to the right sub tree.
• If we encounter a value which is equal to X, we terminate and return true.
• If we encounter a null value, we have traversed the whole tree, and return false.

### Delete Operation

The delete operation is the most complicated operation we’ll implement in this tutorial.

A total of 3 cases can occur when deleting a node from a Binary Search Tree.

• The node to delete is a leaf node (meaning it has no children).
• The node to delete has one child.
• The node to delete has two children.

If we’re deleting a leaf node, all we have to do is to delete that node. Since the node has no children, we don’t have to worry about “reconnecting” other nodes.
When deleting a leaf node, all we have to do is to make parent.right / parent.left = null, according to the leaf node’s position.

Deleting a node with no children

When deleting a node with one child, it is slightly more complicated. Let’s say we want to delete nodeX.

• Traverse to nodeX, and keep track of the parent of nodeX. You must also keep track of which side nodeX exists in its parent (left or right).
• Check which of the sides of nodeX is null. Remember, one of the sides must be null, since we’re deleting a node with only one child.
• Connect nodeX’s “not null” child to nodeX’s parent.

Deleting a node with one child

The hardest case is when we are deleting a node with two children.

To delete a node with two children, one must find the successor.

Successor is the node which will replace the deleted node. Now the question is to how to find it and where to find it.

Successor is the smaller node in the right sub tree of the node to be deleted.

Deleting a node with two children

### Final Implementation of the Binary Search Tree in Java

Note that some of the methods make use of private recursive methods!
New to recursion? Check out our introduction to recursion.

Quick tip: If you wish to expand your Java skill-set and become an advanced Java developer, I highly recommend you to get yourself a copy of the best-selling Effective Java, by Joshua Bloch!