Binary Search Tree (BST) Concrete Implementation In Java

Binary Search Tree is a fundamental data structure that stores items in the memory. In this article, we will learn what is a binary search tree (BST for short) and how to implement one in Java. If you already know about the binary search, then I want to inform you it somehow works like that. However, in BTS, it is a tree data structure, we are going to working with nodes on the tree.

Firstly, what is a binary tree?

The binary tree is an ordered tree data structure that satisfies those properties:

Every node has at most 2 children.
Each child node is labeled either the left child or the right child.
A left child precedes a right child in the order of children with respect to a node.

Binary Search Tree is a node-based binary tree data structure which has the following properties:

The Node’s value of the left child is always lesser than the value of its parent.
The Node’s value of the right child is always greater than the value of its parent.
The left and the right child must also be a BST and there is no duplicate node.

BST Implementation

To implement a binary search tree, we first have to reckon how it might look like. Initially, we discern that in a BTS, each node contains its own value and at most 2 children. Hence, we start making a BST by creating a class named Node, which holds the node’s data and the references to its children, and for better encapsulation, here we are going use this class as a nested class:

public class BST <T extends Comparable<T>>{
    private class Node{
        T element;
        Node left, right;
        public Node(Node left, Node right, T element){
            this.left = left;
            this.right = right;
            this.element = element;
        }
    }
}

Let’s break down what we have inside this Node class. We store our node’s value in a variable named element, each node has 2 references to its left and right child which we store in left and right, respectively. Inside the constructor, we just simply create a typical constructor that assigns the value that we pass in into our instance variables. Notice that here we use the generic type, which means we don’t strict the value that our element variable can have, it could be anything that extends from the Comparable interface. If instead, we use int element or String element, our class can either work with integer or String type at once.

Once we have the Node class on our hand, we move outside and make some addition to work with the tree.

public class BST <T extends Comparable<T>>{
    private Node root = null;
    private int nodeCount = 0;
    // Node class suppressed for brevity
    public boolean isEmpty() {
       return nodeCount == 0;
    }
}

Here we create 2 variables, one for starting our tree named root and the other one nodeCount is for counting the number of the node in a tree. A new method isEmpty() has appeared to check whether the tree is empty.

Common Operations in BST

add(value): adds a value to the tree.
display(): shows all the current node’s values of a tree.
find(node, value): finds whether the tree contains a certain node.
findMin(node): finds the smallest value in the tree.
findMax(node): finds the largest value in the tree.

Insert Element to a Tree

The first thing after we have done with initial steps is finding a way to add a node to the tree. To add a new node to the tree without breaking BST invariant, we need to keep in mind a few things:

If the node’s value we are going to insert is less than the current node’s value, go to the left child of the current node.
If the node’s value we are going to insert is greater than the current node’s value, go to the right child of the current node.
When the current node is null, which means we have reached to the leaf, then insert a new node to this position.

We here insert a new node by using recursion, but you also can use iterative style if you want, and remember, the new node is always added to the leaf of the tree.

private Node insert(Node node, T value) {
    /** We found the leaf node here, then insert the value to this position. */
    if (node == null) {
        node = new Node(null, null, value);
    }
    /**
     * If the value we pass in is less than the current node's value, then we go to the left.
     */
    else if (value.compareTo(node.element) < 0) {
        node.left = insert(node.left, value);

    }
    /**
     * If the value we pass in is greater than the current node's value, then we go to the right.
     */
    else if (value.compareTo(node.element) > 0) {
        node.right = insert(node.right, value);
    }
    /** If the value we pass in already exists in the tree, we return null. */
    else if (value.compareTo(node.element) == 0) {
        return null;
    }
    /** Finally return the node after finishing insertion */
    return node;

}

In the code fragment above, we finally return node. But is it a node we just insert or the whole tree starting from the root? The answer is it returns a binary search tree starting from the root after adding a new value to the correct position.

Insert a new node with the value of 11 to the BST

The insert() method here is labeled as private, hence it intentionally just handle the work inside the BST class. Here we have to create a public method named add():

public void add(T value){
        root = insert(root, value); // inserts value to the correct position by calling the insert method
        nodeCount++; // increases the size of the tree
}

The time complexity of insert() method is $O(lgn)$ . Because each time we traverse the tree, the number of the rest nodes we examine will be cut by a half. However, the worst case is $O(n)$ , but we will talk more about it in upcoming articles on this series.

Display the tree

Next, we are going to create a method that traverses the tree and display the node’s value in the ascending order.

public void display(Node node){
    if(node == null){
       return;
    }
 /** recursively calls display method on the left sub-tree */

        display(node.left);
/** Visit the current node */
        System.out.println("The current node value is " + node.element);
 /** recursively calls display method for the right subtree. */
        display(node.right);
}

Basically, this method will help us print the values of the tree in the ascending order. The left node will be recursively visited first, then we print the value of the root, and then we recursively traverse the right subtree.

For example in the graph above, we first start with the root node F, because this node is not null, then we call the recursive function on its left child, now we have display(node.left) <=> display(F.left), which is B, then it continues until reaches null, and (B.left) stop at A and print this node’s value. After prints value at node A, it moves back to node B because it was previously called but we haven’t done with it yet, prints the node value, and move to the right, e.g (B.right) and go the node D, continues to go to node C, stop prints value at the node C and repeat the identical steps as we did before.

The process of traversing the tree and display the value in ascending order is called In-order traversal. However, we will have another intensive article to talk about this and some other tree traversal methods. The time complexity of this method is $O(n)$

Let’s make some test real quick:

public static void main(String[] args){
        BST binarySearhTree = new BST();
        binarySearhTree.add(12);
        binarySearhTree.add(4);
        binarySearhTree.add(13);
        binarySearhTree.add(7);
        binarySearhTree.add(28);
        binarySearhTree.add(72);
        binarySearhTree.add(1);

        binarySearhTree.display(binarySearhTree.root);
    }

Output:

The current node value is 1
The current node value is 4
The current node value is 7
The current node value is 12
The current node value is 13
The current node value is 28
The current node value is 72

Searching for a node’s value

The work we do here is pretty much equivalent to our insert method. But instead of inserting a new element, it recursively traverses the tree and finds the value we are looking for, returns either true or false if appropriate.

  private boolean contains(Node node, T value){
        /** returns false if we cannot find the value in the tree. */
        if(node == null) return false;
        /** if two values are equal, found it! And returns true. */
        if(value.compareTo(node.element) == 0){
            return true;
        }
        /** Otherwise, recursively go back or right to search for the value. */
        return value.compareTo(node.element) < 0 ? contains(node.left, value) : contains(node.right, value);
        

    }
    public boolean containValue(T value){
        return contains(root, value);
    }

Let’s clarify this thing, the absence of one or more base cases in the recursive method is not acceptable, we firstly create a base case to check if the current node is null, then which indicates there is no value we are searching for out there and returns false. Next, we compare the value with the current node’s value. If it’s less than, go left, if it’s greater than, then go right. The recursive steps run over and over until either we found the value we are searching for in the tree or we cannot find it. The time complexity of this method is $O(lgn)$

Find min and max values of the tree

We take a look at two methods to find the smallest and largest values of the tree, correspondingly. We already know that BST is an ordered tree and the nodes are placed in the sorted order. Hence, the smallest node always is in the leftmost and the largest value is in the rightmost position of the tree, which is noticeable. The time complexity of both methods is $O(lgn)$

/** goes with one direction to the left to the smallest value. */
    public T smallest(Node node){
        while(node.left != null){
            node = node.left;
        }
        return node.element;
    }

    /** goes to the rightmost position to find the largest one. */
    public T largest(Node node){
        while(node.right != null){
            node = node.right;
        }
        return node.element;
    }

The smallest and largest value in a tree.

Finally, to ring the curtain down, here is the complete code of our Binary Search Tree implementation. If you enjoy reading this post, please consider subscribing to my newsletter to update more articles in this series. This code is also available on Github.

public class BST<T extends Comparable<T>> {
    private Node root = null;
    private int nodeCount = 0;

    private class Node {
        T element;
        Node left, right;

        public Node(Node left, Node right, T element) {
            this.left = left;
            this.right = right;
            this.element = element;
        }
    }

    public boolean isEmpty() {
        return nodeCount == 0;
    }

    private Node insert(Node node, T value) {
        /** We found the leaf node here, then insert the value to this position. */
        if (node == null) {
            node = new Node(null, null, value);
        }
        /**
         * If the value we pass in is less than the current node's value, then we go to
         * the left.
         */
        else if (value.compareTo(node.element) < 0) {
            node.left = insert(node.left, value);

        }
        /**
         * If the value we pass in is greater than the current node's value, then we go
         * to the right.
         */
        else if (value.compareTo(node.element) > 0) {
            node.right = insert(node.right, value);
        }
        /** If the value we pass in already exists in the tree, we return null. */
        else if (value.compareTo(node.element) == 0) {
            return null;
        }
        /** Finally return the node after finishing insertion */
        return node;

    }

    public void add(T value) {
        root = insert(root, value);
        nodeCount++;
    }

    public void display(Node node){
    if(node == null){
            return;
    }
 /** recursively calls display method on the left sub-tree */

        display(node.left);
/** Visit the current node */
        System.out.println("The current node value is " + node.element);
 /** recursively calls display method for the right subtree. */
        display(node.right);
  }

    private boolean contains(Node node, T value) {
        /** returns false if we cannot find the value in the tree. */
        if (node == null)
            return false;
        /** if two values are equal, found it! And returns true. */
        if (value.compareTo(node.element) == 0) {
            return true;
        }
        /** Otherwise, recursively go back or right to search for the value. */
        return value.compareTo(node.element) < 0 ? contains(node.left, value) : contains(node.right, value);

    }

    public boolean containValue(T value) {
        return contains(root, value);
    }

    /** goes with one direction to the left to the smallest value. */
    public T smallest(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node.element;
    }

    /** goes to the right most to find the largest one. */
    public T largest(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node.element;
    }

    public static void main(String[] args) {
        BST binarySearhTree = new BST();
        binarySearhTree.add(12);
        binarySearhTree.add(4);
        binarySearhTree.add(13);
        binarySearhTree.add(7);
        binarySearhTree.add(28);
        binarySearhTree.add(72);
        binarySearhTree.add(1);
        System.out.println("Is 12 in the tree? " + binarySearhTree.containValue(12));
        System.out.println("Is 47 in the tree? " + binarySearhTree.containValue(47));
        binarySearhTree.display(binarySearhTree.root);
        System.out.println("The smallest value in the tree is: " + binarySearhTree.smallest(binarySearhTree.root));
        System.out.println("The largest value in the tree is: " + binarySearhTree.largest(binarySearhTree.root));

    }
}