Binary Search Trees in Java

Now that we've seen how a binary tree is structured, lets take a look at one of the most common and powerful implementations - Binary Search Trees.
Binary Search trees are binary trees with some defined rules. Binary search trees can be formed only to nodes which are comparable. By Comparable, i mean which objects in real life that can be compared with each giving outputs as equal, greater or lesser. Numerals are the simplest example of comparables.
The rule of binary search tree follows that all the nodes that are lesser than the root will be on the left and the nodes that are greater than will be on the right. Equal valued nodes can come on either side.
Following is a simple illustration of a binary search tree formed using numerals

The following is a comprehensive Java code on how to construct and then manipulate from a binary tree.

The abstract Data Structure for Tree and the class Node.

package dsa.tree;

public interface Tree {
 public void add(int currentData);
 public Node search(int data);
}

package dsa.tree;

public  class Node {
 Node left;
 Node right;
 Node parent;
 int data;
}

package dsa.tree;

public class BinarySearchTree implements Tree{
 
 private Node root;
 
 public void add(int currentData){
  if(root == null){
   root = new Node();
   root.data = currentData;
   return;
  }
  add(currentData, root);
 }
 
 private void add(int currentData, Node position){
  if(currentData<position.data){
   if(position.left==null){
    position.left = new Node();
    position.left.data = currentData;
    position.left.parent = position;
    return;
   }
   add(currentData, position.left);
  }else{
   if(position.right==null){
    position.right = new Node();
    position.right.data = currentData;
    position.right.parent = position;
    return;
   }
   add(currentData, position.right);
  }
 }
 
 public Node search(int searchData){
  if(root == null){
   return null;
  }
  return search(searchData, root);
 }
 
 /*
  * O(log n) on average case
  */
 private Node search(int searchData, Node node){
  if(node.data == searchData){
   return node;
  }
  if(searchData < node.data){
   return search(searchData, node.left);
  }else{
   return search(searchData, node.right);
  }
 }
 
 public void printOrdered(){
  if(root == null){
   return;
  }
  printOrdered(root);
 }
 
 //DO A IN ORDER TRAVERSAL
 //VISIT LEFT
 //VISIT ROOT
 //VISIT RIGHT
 public void printOrdered(Node node){
  if(node.left != null){
   printOrdered(node.left);
  }
  System.out.println(node.data);
  if(node.right!=null){
   printOrdered(node.right);
  }
 }
 
 public void printValues(){
  print(root);
 }
 
 private void print(Node node){
  if(node == null){
   return;
  }else{
   print(node.left);
   print(node.right);
  }
 }
 
 public static void main(String args[]){
  BinarySearchTree bTree = new BinarySearchTree();
  for(int i=0;i<10;i++){
   int t = (int)(Math.random()*20);
   System.out.println(t);
   bTree.add(t);
  }
  bTree.printValues();
  for(int i=0;i<10;i++){
   int t = (int)(Math.random()*20);
   System.out.println("For i="+t+": "+bTree.search(t));
  }
  System.out.println();
  bTree.printOrdered();
 }
}

We shall discuss about the various features used in this program in the following post.

Bragaadeesh.