Binary Search Tree in Java

In this article, we will take a deeper look at the binary search tree in Java.We will see how to implement the binary search tree in Java and what are its different characteristics.

1. What is Binary Tree

Before we get in the details of binary search tree in Java and how to implement it, it’s very important that we clearly understand what is a binary tree and what are its different characteristics. This will help us when we will implement the binary tree in Java. A binary tree is a non-linear data structure where data objects are generally organized in terms of hierarchical relationship.A binary tree is a tree where every node has 2 for fewer children. We call these nodes as left and right child of binary tree. Here is how a binary tree may look like:

binary search tree in Java

In binary tree, every node contains the following part:

  1. Data (actual data)
  2. pointer to left child.
  3. pointer to right child.

This is how a typical node will look like in Java

public class Node{
  private int data;
  private Node left;
  private Node right;

  public Node(int data){
     this.data= data;
   }
}

Read binary tree data structure to get more understanding about binary tree data structure

2. What is Binary Search Tree

This is a very common question “What is Binary Search tree?“. To put it simply, a binary search tree is a binary tree with the following properties.

  1. Left child is always less than the parent.
  2. Right child is always greater than the parent.
  3. The left and right sub-tree each must be a binary search tree.

The binary search tree allows a faster search and deletion of items from the tree.Binary search tree also known as ordered or sorted binary tree. This is how a BST may look like with the data elements.

binary search tree

There are different opinion as how to store the duplicate values in the binary search tree. Some implementation does not allow duplicate values while others store it on right or left sub-tree. This decision is purely based on the application type.

Binary search tree is one of the fundamental data structure and used to create more abstract data structure like:

  1. Sets.
  2. Multisets.
  3. Associative arrays

3. Binary Search Tree in Java

We will implement a binary search tree in Java. A binary search tree provided the following common operations, and we will implement all these operations.

  1. Inserting Elements.
  2. Search Element in binary search tree.
  3. Delete elements from BST.
  4. Tree Traversal
    1. Depth-First Search
    2. Breadth-First Search

This article aim to provide you understanding of the BST data structure.If you are looking for using the Tree in your production code, consider using TreeMap or similar implementation from JDK. Before we get in to details, Let’s define few basic structures for our binary search tree in Java.

3.1 Binary Search Tree Node

Every node in our binary tree can contain the following information.If you like, you can also define node class as inner class for the Binary search tree class

  1. Actual data (int in our case).
  2. Reference to the left child.
  3. Reference to the right child.
public class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

3.2 Binary Search Tree Class

Next is the Binary search tree class. This class will have the different methods to perform various operations (e.g. insert, delete, search etc.). Here is a high-level overview of the class:

public class BinarySearchTree{
  private Node root;
  //methods for binary search tree
}

Now we have the basic understanding of the Binary search tree and its structure, let’s see how to implement binary search tree in Java. We will start adding a node to the binary search tree.

4. Insert Element to Binary Search Tree

Keep in mind the core property of binary search tree while you insert the key in the tree. The first step is to find the place where we want to insert the key in the binary tree.Also keep in mind that a new node will always be inserted at the leaf. So inserting the node in the binary search tree is a 2-step process – Search + Insert, here is the high level workflow for the insert method.

  1. Start from the root node.
  2. If the new node value is lower than the current node, we go the left child of the current node.
  3. If the value is greater than the current node, go to the right child.
  4. Repeat the step #2 and #3, until the current node is null (leaf node). Insert the node in this position.

We can do most of the operation in BST using loop or through recursion. We will use the recursion for the code, but the same concept can be used if you want to iteration logic.

Let’s assume that we want to add 2 to our binary search tree (see the example in section 2). This is how the operation will look like:

binary search tree in java

Let’s see how the insert code look like and then we will talk about the insert logic.

public class BinarySearchTree {
  private Node root;

  /**
   * Our main insert method which takes the integer as input and will pass
   * the parameter to internal insert method with the root node;
   * @param data
   * @return boolean status.
   */
  public boolean insert(int data) {
      root = insert(root, data);
      return true;
  }

  private Node insert(Node node, int data) {

      /**
       * If Node is null, either tree is empty or this is the
       * leaf node and we can create the node and return the new node.
       */
      if (node == null) {
          return new Node(data);
      }

      /**
       * if data is less than the current element,
       * let's go to the left side of the tree. We are giving a recursive call to the insert method
       * and will wait until response is back.
       */
      if (node.data > data) {
          node.left = insert(node.left, data);
      }

      /**
       * If data is greater than the current element,
       * let's go the right side of the tree.We are giving a recursive call to the insert method
       * and will wait until response is back. Other option is to use while loop.
       */
      if (node.data < data) {
          node.right = insert(node.right, data);
      }
      /**
       * Element already exist is the tree. Please note there are multiple variations for this step.
       * Few implementation do not allow duplicate element in BST (we are using same approach).
       * while other allow duplicate in BST and they can go either to left or right of the tree.
       */
      else{
          return node;
      }
      return node;
  }
}

So the public boolean insert(int data) is the taking user input and we are passing this input to an internal method private Node insert(Node node, int data) with a root node. The root node will help us traverse tree recursively until we get the position where we want to insert the node in the tree. Based on the value in the node and input passed by user, we are moving to either left or right of our tree.Finally, let’s see how to insert tree nodes.

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

         /* We are building a BST as below
              52
           /     \
          15      56
         /  \     /  \
        9    11  54   61
       / \
      3   5 */

        bst.insert(52);
        bst.insert(15);
        bst.insert(56);
        bst.insert(9);
        bst.insert(11);
        bst.insert(54);
        bst.insert(3);
        bst.insert(5);
        bst.insert(61);
    }
}

5. Binary Search Tree Time Complexity

Binary tree is an efficient algorithm. Here is the time complexity for the BST.

  1. The best case time complexity for BST is O(log(n)).
  2. The worst case time complexity for BST is O(h) where h is the height of the binary search tree.

The worst case can happen when we have an unbalanced binary tree. Here, we have to travel from root node to the deepest leaf node before inserting the element. Look at the following image for better clarity and think about adding 5 in the tree. We need to go all the way to the leaf node before we insert the Node (which is equal to the height of the tree).

Unbalanced binary search tree

We can achieve the constant O(log(n)) time complexity for BST in all cases using self balancing tree like AVL or Red-Black Binary tree.

Summary

In this article, we started with the basic of Binary search tree and how to implement binary search tree in Java. I am keeping this article short and will covert the search and deletion in the next lesson. The source code for this series is available on the GitHub.

Subscribe
Notify of

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments