Binary Search Tree Source Code in Java

In this source code example, we will demonstrate how to write a Java program to implement the Binary Search Tree data structure in Java.

A binary search tree (BST) is a type of binary tree that is specifically designed to support fast search operations. It is called a "search tree" because it can be used to search for the presence of a specific element in the tree.

In a BST, the keys in the left subtree of a node are always less than the key in the node, and the keys in the right subtree are always greater. This property allows for efficient search, as the search can be narrowed down to just one subtree by comparing the target key to the key in the current node.

Binary Search Tree Implementation in Java

public class BinarySearchTree {

   private TreeNode root;

   private class TreeNode {
      private int data; // Generic type
      private TreeNode left;
      private TreeNode right;

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

   public void insert(int value) {
      root = insert(root, value);
   }

   public TreeNode insert(TreeNode root, int value) {
      if (root == null) {
         root = new TreeNode(value);
         return root;
      }

      if (value < root.data) {
         root.left = insert(root.left, value);
      } else {
         root.right = insert(root.right, value);
      }
      return root;
   }

   public void inOrder() {
      inOrder(root);
   }

   public void inOrder(TreeNode root) {
      if (root == null) {
         return;
      }
      inOrder(root.left);
      System.out.print(root.data + " ");
      inOrder(root.right);
   }

   public TreeNode search(int key) {
      return search(root, key);
   }

   public TreeNode search(TreeNode root, int key) {
      if (root == null || root.data == key) { // base case 
         return root;
      }

      if (key < root.data) {
         return search(root.left, key);
      } else {
         return search(root.right, key);
      }

   }

   public static void main(String[] args) {
      BinarySearchTree bst = new BinarySearchTree();
      bst.insert(5);
      bst.insert(3);
      bst.insert(7);
      bst.insert(1);

      bst.inOrder();

      System.out.println();

      if (null != bst.search(10)) {
         System.out.println("Key found !!!");
      } else {
         System.out.println("Key not found !!!");
      }
   }
}

Output:

1 3 5 7 
Key not found !!!
Binary search trees are useful for storing data that needs to be quickly retrieved, such as a dictionary or a database index. They are also used in various algorithms, such as in-order tree traversal.