Tuesday, August 13, 2013

Binary Search Tree with In Order Traversal implementation in Java

This class is a complete class you can utilize out of the box for your applications.
Node class can be modified to suit your needs.

class BinaryTreeSearch{
 public enum State{
  Visited, Unvisited,Visiting;
  
 }
 //this is the Node used in the tree
    static class Node{
        private int data;
        private Node left;
        private Node right;
        public Node(int data){
            this.data = data;
            left = null;
            right = null;
        }
        public void setLeft(Node left){
            this.left = left;
        }
        public void setRight(Node right){
            this.right = right;
        }
        public Node getLeft(){
            return this.left;
        }        
        public Node getRight(){
            return this.right;
        }
        public int getData(){
            return this.data;
        }
        public boolean equals(Node n){
            if(this.data ==(int) n.getData()) return true;
            else 
                return false;
        }
    }
    public static void main(String[] args){
        BinaryTreeSearch bts = new BinaryTreeSearch();
        bts.run();
    }
    //execute the test case
    public void run(){
        Node root = new Node(10);
        insert(root,new Node(20));
        insert(root,new Node(5));
        insert(root,new Node(4));
        insert(root,new Node(5));
        insert(root,new Node(15));
        
        inOrderTraverse(root);
        System.out.println("\n" + binarySearch(root,new Node(10)));
    }
    
    // insert a node to the binary search tree
    public void insert(Node root, Node n){
        if(root == null|| n == null) return;
        
        if(root.getData() > n.getData()){
            if(root.getLeft() == null){
                root.setLeft(n);
                 System.out.println("Added node to left of "+root.getData()+" of value "+n.getData());            
            }else{
                insert(root.getLeft(),n);
            }

        }else if(root.getData() < n.getData()){
            if(root.getRight() == null){
                root.setRight(n);
                System.out.println("Added node to Right of "+root.getData()+" of value "+n.getData());      
            }else{
                insert(root.getRight(),n);
            }
            
        }
    }
    //in-order Traversal
    public void inOrderTraverse(Node root){
        if(root != null){
            inOrderTraverse(root.getLeft());
            System.out.print("  "+root.getData());
            inOrderTraverse(root.getRight());
        }
        
    }
    //binary search
    public boolean binarySearch(Node root,Node n){
        if(root == null || n == null) {
            return false;
        }
        System.out.println("  Testing out "+root.getData()+" for value "+n.getData());
        if(root.getData() > n.getData()){
           return  binarySearch(root.getLeft(),n);
        }else if(root.getData() < n.getData()){
           return  binarySearch(root.getRight(),n);
        }
        return true;
    }
}

11 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. //binary search
    public boolean binarySearch(Node root,Node n){
    if(root == null || n == null) {
    return false;
    }
    System.out.println(" Testing out "+root.getData()+" for value "+n.getData());
    if(root.getData() > n.getData()){
    return binarySearch(root.getLeft(),n);
    }else if(root.getData() < n.getData()){
    return binarySearch(root.getRight(),n);
    }
    return true;
    }

    I think this particular code is incorrect and will always return true even for the values not present in the BST. The correct implement should have either "false" or "true" be returned something like this

    private boolean binarySearch(Node root, Node node) {

    if(root == null || node == null)
    return false;
    else{
    if(root.getData() == node.getData())
    return true;
    else if(root.getData() > node.getData())
    return binarySearch(root.left, node);
    else
    return binarySearch(root.right, node);
    }
    }

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. Great Job !
      Just a small change you might wanna make to the above code as even for the non-existing values, binarySearch() still returns a 'true' value.
      One more verification step to verify
      if(root.getData() == n.getData())
      return true;

      Delete
  3. No Man...
    code of binarySearch(...) is correct and work well...

    Thanks

    ReplyDelete
  4. Hi.. can you show how a delete would work as well please?

    ReplyDelete
  5. Really Nice Information,Thank You Very Much For Sharing.
    Web Designing Company

    ReplyDelete