Binary Search Tree Implementation in Java

Binary Search Tree is a special type of Binary Tree where nodes are arranged in order: for each node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater-or-equal to the node. Binary search trees are efficient in insert and lookup operations. On average it can locate a node in lg(n) time (i.e. log base 2).

BST is also known as Ordered Binary Tree. Below is the Java code of a binary search tree. The attribute, root of the class points to the root node of the tree. The nested Node<E> class is made private, as it is used only for internal storage inside the binary search tree and is not exposed for clients. Also, Node<E> encapsulates the state properly and exposes them only through interfaces (i.e. getters and setters).

   
 /**  
  * Java implementation of a Binary Search Tree through a generic node. You can  
  * store any data type in it provided compareTo method is properly implemented  
  *  
  * @author Siddheshwar  
  */  
   
 public class BST<E extends Comparable<E>> {  
      /**  
       * Pointer to the root node of the tree  
       */  
      Node<E> root;  
   
      /**  
       * Adds a new node to the tree  
       */  
      public void add(Node<E> t) {  
           if (t == null)  
                return;  
   
           if (root == null) {  
                root = t;  
           } else {  
                Node<E> r = root; // required so that root doesn't get overridden  
                add(r, t);  
           }  
      }  
   
      /**  
       * Internal method to add node to the tree  
       */  
      private void add(Node<E> root, Node<E> t) {  
           if (root == null || t == null)  
                return;  
   
           int cmp = t.compareTo(root);  
   
           if (cmp >= 0) {  
                if (root.getRight() != null)  
                     add(root.getRight(), t);  
                else {  
                     root.setRight(t);  
                     return;  
                }  
           }  
           if (cmp < 0) {  
                if (root.getLeft() != null)  
                     add(root.getLeft(), t);  
                else {  
                     root.setLeft(t);  
                     return;  
                }  
           }  
      }  

      /**  
       * In-order traversal method to print the tree in sorted way  
       */  
      public void inorderTraversal(Node<E> root) {  
           if (root != null) {  
                inorderTraversal(root.getLeft());  
                System.out.print(root.getData() + " ");  
                inorderTraversal(root.getRight());  
           }  
      }  
   
      /**  
       * Node class to represent each node of the tree  
       */  
      private class Node<E extends Comparable<E>> implements Comparable<Node<E>> {  
           E data;  
           Node<E> left;  
           Node<E> right;  
   
           public Node(E d) {  
                this.data = d;  
                this.left = null;  
                this.right = null;  
           }  

           public E getData() {  
                return data;  
           }  
   
           public Node<E> getLeft() {  
                return left;  
           }  
   
           public void setLeft(Node<E> left) {  
                this.left = left;  
           }  
   
           public Node<E> getRight() {  
                return right;  
           }  
   
           public void setRight(Node<E> right) {  
                this.right = right;  
           }  
   
           @Override  
           public int compareTo(Node<E> node) {  
                return this.data.compareTo(node.data);  
           }  
      }  
   
      /**  
       * Creates a new node and then adds it to the tree  
       */  
      private void insert(int num) {  
           Node<Integer> t = new Node<Integer>(num);  
           add((Node<E>) t);  
      }  
   
      /**  
       * Method to test the tree construction  
       */  
      public static void main(String[] args) {  
           BST<Integer> bst = new BST<Integer>();  
           bst.insert(10);  
           bst.insert(20);  
           bst.insert(5);  
           bst.insert(50);  
           bst.insert(7);  
           bst.insert(7);  
           System.out.println(" Tree in Sorted order :");  
           bst.inorderTraversal(bst.root);  
      }  
 }  
   

Output:
Tree in Sorted order :
5 7 7 10 20 50

Some Important Problems on Binary Tree :
http://cslibrary.stanford.edu/110/BinaryTrees.html

Related Post : Linkedlist Implementation in Java