Java Code House

Today in this article I will tell you how to create a generic binary search tree (BST) in Java. A normal binary tree is any tree where each node can have a maximum of 2 nodes. But binary search tree is a special kind of binary tree which when traveresed using inorder traversal algorithm lists the nodes in ascending order. In this article we will not deal with traversal, and only concentrate on creating and generating the BST.
     The code is written to support generics. This means that only one code has to be written for binary search tree(BST). You can insert anything in the tree but the objects must be comparable. Comparable objects here means that classes of those objects must extend java.lang.Comparable interface. The comments are also added to the code in Javadoc style

    Here in our code we have a class called BinarySearchTree, a generic class with type parameter T; which contains an inner class Node. The node class is used to define each node of the tree - containing two pointers for left and right sub-tree and a value parameter to contain value of the node. Next is insert(T) method which is called by the user to insert new nodes. This function adds root if tree is empty, otherwise calls a private insert(Node,T) method with root node and vakue passed as parameter. The private inner(Node,T) is a recursive one which adds node recursively depending on the value - added to left sub-tree if less than parent else added to right sub-tree. The other two methods are very trivial isEmpty() to check if tree is empty and peek() to return the value of root.
-------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------

public class BinarySearchTree<T extends Comparable<T>> {
 //T is the type parameter and comparable
 Node root;  //root node of the tree
 
 //defines each node of tree
 class Node{
  T value;  //value of node
  Node right,left;  //pointer to left and right sub-tree
  
  Node(T value){
   this.value = value;
  }
 }
 
 /**
  * This method inserts new node in tree
  * @param value
  */
 public void insert(T value){
  if(isEmpty())
   root = new Node(value);  //root node added
  else
   insert(root, value);  //if not empty then insert based on root
 }
 
 /**
  * Recursive method is called internally to insert nodes at proper 
    places depending on their vakues.
  * @param node
  * @param value
  */
 private void insert(Node node, T value){
  if(value.compareTo(node.value) < 0){  //if new value less than parent node
   if(node.left == null)  //if left null then add
    node.left = new Node(value);
   else
    insert(node.left,value);  //if left not null then recursive call
  }
  else if(value.compareTo(node.value) >= 0){  //if new value same or greater than parent node
   if(node.right == null)  //if right null then add
    node.right = new Node(value);
   else
    insert(node.right,value);  //if right not null then recursive call
  }
 }
 
 /**
  * Returns the value of the root
  * @return
  */
 public T peek(){
  return root.value;
 }
 
 /**
  * Checks if tree is empty or not
  * @return
  */
 public boolean isEmpty(){
  return (root == null)? true : false;
 }
}

Download Links