BinarySearchTree.java

package Tree;

import org.w3c.dom.ls.LSOutput;

public class BinarySearchTree {

    /*
    
    without recursion
    
    Node root;

    public void insertion(int val)
    {
        Node newnode = new Node(val);

        if (root == null)
        {
            root = newnode;
            System.out.println( val + " is inserted as root");
        }
        else
        {
            Node current = root;
            Node parent = null;
            while (true) {
                if (val < current.data)
                {
                    current = current.left;
                    if (current==null)
                    {
                        current = newnode;
                        System.out.println(val +" is inserted at left");
                        return;
                    }
                }
                else
                {
                    current = current.right;
                    if (current == null)
                    {
                        current = newnode;
                        System.out.println(val + " is inserted at right ");
                        return;
                    }
                }
            }
        }
    }
    
     */
    
//    By recursion
    
    public static Node insertionByrecursion(Node root , Node newnode)
    {
        if (root ==null)
        {
            root = newnode;
            return root ;
        }
        if (root.data> newnode.data)
        {
            if (root.left == null)
            {
                root.left = newnode;
            }
            else 
            {
                insertionByrecursion(root.left,newnode);
            }
        }
        else if (root.data < newnode.data)
        {
            if (root.right == null)
            {
                root.right = newnode;
            }
            else
            {
                insertionByrecursion(root.right , newnode);
            }
        }
        return root;
    }
    
    public  void preorder(Node root)
    {
        if (root==null)
        {
            return;
            
        }
        System.out.println(root.data);
        preorder(root.left);
        preorder(root.right);
    }
    
    
    public static boolean search(Node root , Node searchnode)
    {
        if (root ==null)
            return false;
        if (root.data == searchnode.data)
            return true;
        
        boolean result = false;
        
        if (root.data > searchnode.data) {
            result = search(root.left, searchnode);
        }        
        else if (root.data< searchnode.data)
            result = search(root.right,searchnode); 
        
        return result;
    }

}

/*

class Test
{
    public static void main(String[] args) {

        BinarySearchTree obj = new BinarySearchTree();
        obj.insertion(15);
        obj.insertion(20);
        obj.insertion(10);
        obj.insertion(5);
    }
}

 */