CS 15-121 Introduction to Data Structures                 Lab 5

	1. Create a java project called "BinarySearchTree". In it, create a package called "binarysearchtree".
	2. Copy and paste the code that's provided below, creating new files for each class.
	3. Read up about Binary search trees here: https://en.wikipedia.org/wiki/Binary_search_tree. Check the main method in the BinarySearchTree class, where numbers are being inserted into the tree. Draw the tree on paper.
	4. There is a bug in the "addNode" method of the BinarySearchTree class. Find it and fix it.
	5. We can travel through a tree and print it's elements in many ways. Some tree traversal methods are listed here: https://en.wikipedia.org/wiki/Tree_traversal. Level order/Breadth first tree traversal visits every node at a particular level before moving to the next level. For example, the level order traversal for the tree you drew will be 31,7,56,6,27,34,89,2,11,33,45,70,92,42,55. We will be using queues for this task. There is a method in the BinarySearchTree class called LevelOrderTraversal, which has the pseudocode for printing the level-order traversal of a tree. Implement it. 
	6. There is a bug in one of the methods in the Queue class. Find it and fix it.
	7. Finally, write a method to search for a given element in the tree. If the element is found, return true. Otherwise, return false.
	
	
	************************************************************************
	BinarySearchTree.java
	
	package binarysearchtree;


/**
 *
 * @author Aradhana
 */
public class BinarySearchTree {

    /**
     * @param args the command line arguments
     */
    TreeNode root;
    Queue q;
    
    BinarySearchTree()
    {
        root = null;
        q = new Queue();
    }
    
    public void addNode(int n)
    {
        if(root == null)
        {
             root = new TreeNode(n);
        }
        else
        {
            TreeNode node = root;   //used to keep track of your current node
            TreeNode parent = null; //used to keep track of the parent node
            while(node!=null)
            {
                parent = node;
                if(node.getData() > n) 
                    node = node.getRchild();
                else
                    node = node.getLchild();
            }
            
            int data = parent.getData();
            if(data < n)
            {
                parent.setRchild(new TreeNode(n));
            }
            else
            {
                parent.setLchild(new TreeNode(n));
            }
        }
    }
    
    public void LevelOrderTraversal()
    {
        LevelOrderTraversal(root);
    }
    
    public void LevelOrderTraversal(TreeNode t)
    {
        if(t==null)
        { 
            return;
        }
          
        /*  insert the node t into the queue, since it is not null
            until the queue becomes empty, do the following:
                -remove a node from the queue
                -print the node's data
                -insert the node's left child into the queue, if it is not null
                -insert the node's right child ino the queue, if it is not null
            
        */   
           
                
    }
        
    
   
    
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.addNode(31);
        bst.addNode(56);
        bst.addNode(34);
        bst.addNode(7);
        bst.addNode(6);
        bst.addNode(89);
        bst.addNode(45);
        bst.addNode(33);
        bst.addNode(27);
        bst.addNode(92);
        bst.addNode(70);
        bst.addNode(42);
        bst.addNode(55);
        bst.addNode(11);
        bst.addNode(2);
        bst.LevelOrderTraversal();
        int len = bst.q.getLength();
         for(int i=0;i<len;i++)
            {
                System.out.println(bst.q.remove());
            }
        
    }
    
}
****************************************************************************
TreeNode.java


package binarysearchtree;


public class TreeNode {
    private int data;
    private TreeNode lchild;
    private TreeNode rchild;
    
    TreeNode()
    {
        data = 0;
        lchild = null;
        rchild = null;
    }
    
    TreeNode(int d)
    {
        data = d;
        lchild = null;
        rchild = null;
    }
    
    public int getData()
    {
        return data;
    }
    public void setData(int n)
    {
        data = n;
    }      
    public TreeNode getLchild()
    {
        return lchild;
    }
    public void setLchild(TreeNode n)
    {
        lchild = n;
    }
    public TreeNode getRchild()
    {
        return rchild;
    }
    public void setRchild(TreeNode n)
    {
        rchild = n;
    }
    
}

****************************************************************************
Queue.java

package binarysearchtree;


public class Queue {
    TreeNode arr[];
    int front;
    int rear;
    int length = 0;
    
    Queue()
    {
        arr = new TreeNode[30];
        front = 0;
        rear = 0;
    }
    
    void insert(TreeNode n)
    {
        arr[rear++] = n;
        length++;
    }
    
    TreeNode remove()
    {
        if(!(front>rear))
        {
            length--;
            return arr[front++];
        }
        return null;
    }
    
    int getLength()
    {
        return length;
    }
    
    boolean isEmpty()
    {
        return (front==rear) ? false:true;
    }
    
}
****************************************************************************