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.

tree data structure

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.

Binary Search Tree implementation

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.

/**
 * Node in a Binary Search Tree.
 * The node contains a key (it's value), and a reference to the right and left node (its children).
 * <p>
 * The variables in the class are package-private. No getter's and setter's needed.
 *
 * @author Anders Engen Olsen
 */
class Node<AnyType> {

    AnyType value;
    Node<AnyType> left, right;

    Node(AnyType value) {
        if (value == null)
            throw new IllegalArgumentException("Value can't be null");

        this.value = value;
        left = right = null;
    }
}
import org.junit.Before;
import org.junit.Test;

import static org.junit.Assert.*;

/**
 * Test for the Node class.
 *
 * @author Anders Engen Olsen
 * @see Node
 */
public class NodeTest {

    private Node<Integer> node;
    private Integer nodeValue;

    @Before
    public void setUp() {
        nodeValue = 1;
        node = new Node<>(nodeValue);
    }

    @Test
    public void testNodeHasCorrectValue() {
        assertEquals(nodeValue, node.value);
    }

    @Test
    public void testNodeHasNoChildren() {
        assertNull(node.left);
        assertNull(node.right);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testNodeNullConstructorThrowsException() {
        Node<Integer> node = new Node<>(null);
    }
}

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.

/**
 * Binary Search Tree.
 *
 * @author Anders Engen Olsen
 */
public class BinarySearchTree<AnyType> {

    private Node<AnyType> root;
    private int size;

    /**
     * Default constructor, constructing an empty tree.
     */
    public BinarySearchTree() {
        root = null;
        size = 0;
    }

    /**
     * Returning size of the search tree
     *
     * @return size
     */
    public int size() {
        return size;
    }

    /**
     * @return true if tree is empty, size = 0.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Searching for a node in the bst
     *
     * @param x The value to search for
     * @return true if found
     */
    public boolean find(AnyType x) {
        return false;
    }

    /**
     * Deleting a node in the best
     *
     * @param x The value to delete
     * @return true if found and deleted
     */
    public boolean delete(AnyType x) {
        return false;
    }

    /**
     * Inserting a Node in the binary search tree.
     *
     * @param x value to insert
     */
    public void insert(AnyType x) {

    }
}

As always, tests are written!

import org.junit.Before;
import org.junit.Test;

import static org.junit.Assert.*;

/**
 * Test for the BinarySearchTree class.
 *
 * @author Anders Engen Olsen
 * @see BinarySearchTree
 */
public class EmptyBinarySearchTreeTest {

    private BinarySearchTree<Integer> bst;

    @Before
    public void setUp() {
        bst = new BinarySearchTree<>();
    }

    @Test
    public void testBstHasSizeOfZero() {
        assertEquals(0, bst.size());
    }

    @Test
    public void testBstIsEmptyReturnsTrue() {
        assertTrue(bst.isEmpty());
    }
}

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 in a binary search tree
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 in a binary search tree
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 in a binary search tree
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.

import java.util.NoSuchElementException;

/**
 * Binary Search Tree.
 *
 * @author Anders Engen Olsen
 */
public class BinarySearchTree<AnyType extends Comparable> {

    private Node<AnyType> root;
    private int size;

    /**
     * Default constructor, constructing an empty tree.
     */
    public BinarySearchTree() {
        root = null;
        size = 0;
    }

    /**
     * Returning size of the search tree
     *
     * @return size
     */
    public int size() {
        return size;
    }

    /**
     * @return true if tree is empty, size = 0.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Searching for a node in the bst
     *
     * @param x The value to search for
     * @return true if found
     */
    public boolean find(AnyType x) {
        return findRecursively(root, x);
    }

    /**
     * Private recursive method to findRecursively a value in the BST
     *
     * @param root root node
     * @param x    value to findRecursively
     * @return true if found value == x.
     */
    private boolean findRecursively(Node<AnyType> root, AnyType x) {
        // If root is null the node is not present
        if (root == null)
            return false;
        // It is present
        if (root.value.compareTo(x) == 0)
            return true;

        // The value is greater
        if (root.value.compareTo(x) > 0)
            return findRecursively(root.left, x);

        // The value is less
        return findRecursively(root.right, x);
    }

    /**
     * Deleting a node in the best
     *
     * @param x The value to delete
     * @return true if found and deleted
     */
    public Node<AnyType> delete(AnyType x) {
        return deleteRecursively(root, x);
    }

    /**
     * Deleting recursively
     *
     * @param root root node
     * @param x    value to delete
     * @return deleted node
     */
    private Node<AnyType> deleteRecursively(Node<AnyType> root, AnyType x) {
        // Traversed the whole tree, returning false
        if (root == null)
            throw new NoSuchElementException("Not found!");

        // Traversing
        if (x.compareTo(root.value) < 0)
            root.left = deleteRecursively(root.left, x);
        else if (x.compareTo(root.value) > 0)
            root.right = deleteRecursively(root.right, x);

        else {
            size--;

            // node with only one child or no child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            // node with two children: Get the inorder successor (smallest
            // in the right subtree)
            root.value = minValue(root.right);

            // Delete the inorder successor
            root.right = deleteRecursively(root.right, root.value);
        }
        return root;
    }

    AnyType minValue(Node root) {
        AnyType minv = (AnyType) root.value;
        while (root.left != null) {
            minv = (AnyType) root.left.value;
            root = root.left;
        }
        return minv;
    }

    /**
     * Inserting a Node in the binary search tree.
     *
     * @param x value to insert
     */
    public void insert(AnyType x) {
        root = insertRecursively(root, x);
        size++;
    }

    /**
     * Private recursive method to insert a node.
     *
     * @param root
     * @param x
     * @return
     */
    private Node<AnyType> insertRecursively(Node<AnyType> root, AnyType x) {

        // Tree is empty, inserting at root
        if (root == null) {
            root = new Node<>(x);
            return root;
        }

        // Traversing the tree recursively
        if (x.compareTo(root.value) < 0)
            root.left = insertRecursively(root.left, x);
        else if (x.compareTo(root.value) > 0)
            root.right = insertRecursively(root.right, x);
        else {
            // Duplicate element!
            throw new IllegalArgumentException("No duplicates allowed!");
        }

        return root;
    }
}
import org.junit.Before;
import org.junit.Test;

import java.util.NoSuchElementException;

import static org.junit.Assert.*;

/**
 * Test for the BinarySearchTree.
 *
 * @author Anders Engen Olsen
 */
public class BinarySearchTreeTest {

    private BinarySearchTree<Integer> bst;

    @Before
    public void setUp() {
        bst = new BinarySearchTree<>();
    }

    @Test
    public void testInsertElementInBSTSizeIncreases() {
        bst.insert(1);
        assertEquals(1, bst.size());
    }

    @Test(expected = IllegalArgumentException.class)
    public void testInsertDuplicateThrowsException() {
        populateBST();
        bst.insert(1);
    }

    @Test
    public void testTenElementsGiveSizeOfTen() {
        populateBST();
        assertEquals(10, bst.size());
    }

    @Test
    public void testFindElementInBSTTrueWhenPresent() {
        populateBST();
        assertTrue(bst.find(4));
    }

    @Test
    public void testFindElementInBSTFalseWhenNotPresent() {
        populateBST();
        assertFalse(bst.find(11));
    }

    @Test
    public void testDeleteElementSizeDecreases() {
        populateBST();
        bst.delete(1);
        assertEquals(9, bst.size());
    }

    @Test(expected = NoSuchElementException.class)
    public void testDeleteNotPresentThrowsException() {
        populateBST();
        bst.delete(11);
    }

    /**
     * Populating the BST with 0-9, total of 10 elements.
     */
    private void populateBST() {
        for (int i = 0; i < 10; i++) {
            bst.insert(i);
        }
    }
}