Friday, October 23, 2015

How to implement Binary Search tree in Java? Example

A binary search tree or BST is a popular data structure which is used to keep elements in order. A binary search tree is a binary tree where the value of a left child is less than or equal to the parent node and value of the right child is greater than or equal to the parent node. Since its a binary tree, it can only have 0, 1 or two children. What makes a binary search tree special is its ability to reduce the time complexity of fundamental operations like add, remove and search, also known as insert, delete and find. In a BST, all these operations (insert, remove and find) can be performed in O(log(n)) time. The reason for this improvement in speed is because of the unique property of binary search tree, where for each node, the data in the left child is less than (or equal) and the data in the right child is greater than (or equal) to the data in said node.

In Programming interviews, you will see many data structure and algorithmic questions based upon binary search tree e.g. check if a binary tree is a BST or not? Or, write a program to check if BST is balanced or not. In order to solve that problem, you must know how to implement BST in Java.

In this tutorial, I will teach you how to implement a binary search tree in Java, which you can use to solve any binary search tree or binary tree based coding problems.

Binary Search tree in Java

Here, You will learn how to create a binary search tree with integer nodes. I am not using Generics just to keep the code simple but if you like you can extend the problem to use Generics, which will allow you to create a Binary tree of String, Integer, Float or Double. Remember, you make sure that node of BST must implement the Comparable interface. This is what many Java programmer forget when they try to implement binary search tree with Generics.

Here is an implementation of a binary search tree in Java. It's just a structure, we will subsequently add methods to add a node in a binary search tree, delete a node from binary search tree and find a node from BST in the subsequent part of this binary search tree tutorial.

In this implementation, I have created a Node class, which is similar to our linked list node class, which we created when I have shown you how to implement linked list in Java. It has a data element, an integer and a Node reference to point to another node in the binary tree.

I have also created four basic functions, as shown below:
  •  getRoot(), returns the root of binary tree
  •  isEmpty(), to check if binary search tree is empty or not
  •  size(), to find the total number of nodes in a BST
  •  clear(), to clear the BST

For a curious developer who wants to learn advanced data structure in Java, I also recommend checking out Data Structures and Algorithms in Java, 2nd edition, one of the rare book where you will find examples in Java.

How to implement BST in Java

Here is the sample code to create a binary search tree or BST in Java, without using any third party library.

Binary Search Tree in Java

Java Program to represent Binary Search Tree or BST

import java.util.Stack;

 * Java Program to implement a binary search tree. A binary search tree is a
 * sorted binary tree, where value of a node is greater than or equal to its
 * left the child and less than or equal to its right child.
 * @author WINDOWS 8
public class BST {

    private static class Node {
        private int data;
        private Node left, right;

        public Node(int value) {
            data = value;
            left = right = null;

    private Node root;

    public BST() {
        root = null;

    public Node getRoot() {
        return root;

     * Java function to check if binary tree is empty or not
     * Time Complexity of this solution is constant O(1) for
     * best, average and worst case. 
     * @return true if binary search tree is empty
    public boolean isEmpty() {
        return null == root;

     * Java function to return number of nodes in this binary search tree.
     * Time complexity of this method is O(n)
     * @return size of this binary search tree
    public int size() {
        Node current = root;
        int size = 0;
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || current != null) {
            if (current != null) {
                current = current.left;
            } else {
                current = stack.pop();
                current = current.right;
        return size;

     * Java function to clear the binary search tree.
     * Time complexity of this method is O(1)
    public void clear() {
        root = null;


That's all in this tutorial about how to implement binary search tree in Java. In this tutorial, you have learned to create the structure of BST using Node class and some basic function. In next couple of tutorials, you will learn some more interesting things with BST e.g. writing a method to add Nodes in BST, this method must make sure that property of binary search tree is not violated. I mean, it first needs to find a right place and then needs to add the element. Subsequently, you will also learn how to search a node in binary search tree.

Further Reading
If you are interested in learning Data structure and Algorithm in Java Programming language then you can following books which have several examples of the tree, linked list, heap and other advanced data structure in Java.
Algorithms and Data Structures - Part 1
Algorithms and Data Structures - Part 2
Introduction to Algorithms

Data Structure and Algorithm in Java
If you like this tutorial and interested in more Java tutorials on Data Structure and algorithmic concepts then check out following articles as well:
  • 5 Data Structure and Algorithm Books for Java Developers (list)
  • 30 Array-based questions from Programming interviews (article)
  • Sieve of Eratosthenes algorithms for Prime numbers (algorithm)
  • How to reverse an array in place? (solution)
  • 20 String based questions from Programming Job Interviews (article)
  • How to implement Insertion sort algorithm in Java? (solution)
  • How to find all pairs in array of ints whose sum is equal to k (solution)
  • How to remove duplicates from an array in Java? (solution)
  • How to check if linked list contains a loop or not? (algorithm)


VJosh said...

please put some more algorithm questions and how they can be implemented in java or else the explanation to various algorithms and why they are so popular?

Jane Rose said...


Javin Paul said...

Hello @Jane Rose, glad to hear that you like this article about binary tree in Java. Don't forget to share with your friends, it helps a lot.

shrikrishna kadam said...

Hi Javin,

Will the BST allows child value equal to it's parent?
I read somewhere that this is a special case and we need to handle this specially?

I'm confused as you said equal values of parent and child are allowed in BST


Javin Paul said...

Hello kadam, if duplicate keys are allowed in binary search tree (BST), then nodes with values that are equal to the key in node n (parent node) can be either in n's left subtree or in its right subtree (but not both).

Post a Comment