All About Binary Search Trees, In Java

If you’re pursuing a degree in computer science, you’ll probably experience Binary Trees in one of your first semesters of school. After seeing them in one of those first semesters, you probably won’t see them again until you’re interviewing for a job.

While interviewing for software engineering or programming positions, you may get many questions regarding Binary Trees and Binary Search Trees. Take this as a refresher in case this is a subject you might have forgotten over the years.

If you’re unfamiliar with binary trees, take the following diagram as an example:

Binary trees via Wikipedia:

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

The diagram I listed, particularly represents a Binary Search Tree (BST) in which all left child nodes are less than their parents right child nodes and the parent itself.

For the rest of this article, we’re going to be interested in Binary Search Trees and we’re going to be thinking in Java.

public class TreeNode {

    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

}

The above code represents a node in our BST.

There are a few things we’ll need when designing our Binary Search Tree class:

• Insert new nodes following the rules of the tree
• Delete a node from the tree
• Print all nodes from greatest to smallest
• Print all nodes from smallest to greatest

So let’s take a look at our BST class:

public class BST {

    TreeNode root;

    public BST(TreeNode root) {
        this.root = root;
    }

    public void insert(int value) { }

    public void delete(int value) { }

    public void printRightToLeft(TreeNode node) { }

    public void printLeftToRight(TreeNode node) { }

}

Let’s start by looking at the insert functionality of this tree. We know that we want to insert a node only where it makes sense. Take the diagram at the top of this post for example. Let’s say we are just now building it and we are starting with node value 10. We now are given node value 5, which is less than 10 so it is placed as a left child. Then we are given node value 9 which is less than 10, but greater than 5, so it is now the right child of node 5. This process continues until our tree is complete.

public void insert(int value) {
    if(root == null) {
        this.root = new TreeNode(value);
    } else {
        this.root = insert(this.root, value);
    }
}

Wait a second! The above insert statement is accepting only a value, so how are we going to work with nodes? Well, we need to overload a Java function that takes nodes and values because we are going to recursively insert our new node.

private TreeNode insert(TreeNode node, int value) {
    if(node == null) {
        return new TreeNode(value);
    } else if(node.value < value) {
        node.right = insert(node.right, value);
    } else if(node.value > value) {
        node.left = insert(node.left, value);
    }
    return node;
}

That was easy! Following the logic of Binary Search Trees, we’ve now created two functions to populate one. The next thing we want to do is print out our tree both in ascending and descending order. This can be done with two similar functions that have a time complexity of O(log(n)):

public void printRightToLeft(TreeNode node) {
    if(node != null) {
        if(node.right != null) {
            printRightToLeft(node.right);
        }
        System.out.println(node.value);
        if(node.left != null) {
            printRightToLeft(node.left);
        }
    }
}

public void printLeftToRight(TreeNode node) {
    if(node != null) {
        if(node.left != null) {
            printLeftToRight(node.left);
        }
        System.out.println(node.value);
        if(node.right != null) {
            printLeftToRight(node.right);
        }
    }
}

In the above two functions, printRightToLeft(TreeNode node) will print all the node values starting at a given node in descending order or greatest to smallest. The function printLeftToRight(TreeNode node) will do the same thing but return all node values in ascending order. If you wanted to fancy things up you could also include these two functions in your code, making the others overloaded:

public void printRightToLeft() {
    printRightToLeft(this.root);
}

public void printLeftToRight() {
    printLeftToRight(this.root);
}

So where does that leave us? We still need to come up with a way for deleting nodes from our tree.

Let’s take a look at the following function:

public void delete(int value) {
    this.root = delete(this.root, value);
}

Wait a second, this looks like what we did for the insert(int value) method. It is, so we’re going to need to overload it again with the following code:

public TreeNode delete(TreeNode node, int value) {
    if(node.value < value) {
        node.right = delete(node.right, value);
    } else if(node.value > value) {
        node.left = delete(node.left, value);
    } else {
        if(node.right == null) {
            return node.left;
        }
        if(node.left == null) {
            return node.right;
        }
        TreeNode temp = node;
        node = min(temp.right);
        node.right = deleteMin(temp.right);
        node.left = temp.left;
    }
    return node;
}

The whole point here is to traverse down the tree until we find the desired value to delete. When it is found, we need to make some judgment calls in how to process any child elements that this node might have.

The goal here is to find the lowest left node on the right child of the node for deletion. Take the diagram for example. If we want to delete the root node 10, then our new root node will be 11, and node 12 will be its right child.

Here is the min(TreeNode node) function that we used to find node 11:

private TreeNode min(TreeNode node) {
    if(node.left == null) {
        return node;
    } else {
        return min(node.left);
    }
}

And here is the deleteMin(TreeNode node) function that we used to find node 12:

private TreeNode deleteMin(TreeNode node) {
    if(node.left == null) {
        return node.right;
    }
    node.left = deleteMin(node.left);
    return node;
}

All of this can be a little confusing, but it works great.

Conclusion

Although we went over the basics behind Binary Search Trees, there is still a lot to learn. For example, there are still Balanced Binary Search Trees that I haven’t discussed. However, lucky for us, in an interview it may be less probable to see some of this complex BST stuff. Knowing how to insert, delete, and traverse a BST is most of the battle.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.