import java.util.*;
public class BNode {
    int data;
    BNode left,right;
    public BNode(int data)
    {
        this.data=data;
        left=right=null;
    }

}
class BST
{
    private BNode root;
    public BST()
    {
        root=null;
    }
    public BNode father(BNode p)
    {
        if(p==root)
            return null;
        BNode q=root;
        while(q!=null)
        {
            if(q.left==p||q.right==p)
                return q;
            if(p.data<=q.data)
                q=q.left;
            else q=q.right;
        }
        return null;
    }
    public void insert(int ele)
    {
        BNode p=new BNode(ele);
        if(root==null)
            root=p;
        else
        {
            BNode q=root;
            while(q!=null)
            {
                if(ele<=q.data)
                    if(q.left==null)
                    {
                        q.left=p;
                        break;
                    }
                    else q=q.left;
                else if(q.right==null)
                {
                    q.right=p;
                    break;
                }
                else q=q.right;
            }
        }
    }
    public boolean search(int ele)
    {
        BNode q=root;
        while(q!=null)
        {
            if(q.data==ele)
                return true;
            if(ele<q.data)
                q=q.left;
            else q=q.right;
        }
        return false;
    }
    public void inorder(BNode x)
    {
        if(x!=null)
        {
            inorder(x.left);
            System.out.print(x.data+" ");
            inorder(x.right);
        }
    }
    public BNode getRoot()
    {
        return root;
    }
}
class BSTExp
{
    public static void main(String args[])
    {
        Scanner src=new Scanner(System.in);
        BST obj=new BST();
        while(true)
        {
            System.out.println("\n1.Insert in tree 2.Search element 3.Exit");
            int ch=src.nextInt();
            int ele;
            if(ch==3)
                break;
            switch(ch)
            {
                case 1:System.out.println("Enter the element to insert");
                ele=src.nextInt();
                obj.insert(ele);
                obj.inorder(obj.getRoot());
                break;

                case 2:System.out.println("Enter the element to search");
                ele=src.nextInt();
                if(obj.search(ele))
                    System.out.println(ele+" is Found");
                else System.out.println(ele+" is Not Found");
                break;

                default:System.out.println("Invalid choice");
            }
        }
    }
}

O/P:

1.Insert in tree 2.Search element 3.Exit
1
Enter the element to insert
12
12 
1.Insert in tree 2.Search element 3.Exit
1
Enter the element to insert
56
12 56 
1.Insert in tree 2.Search element 3.Exit
1
Enter the element to insert
67
12 56 67 
1.Insert in tree 2.Search element 3.Exit
1
Enter the element to insert
78
12 56 67 78 
1.Insert in tree 2.Search element 3.Exit
1
Enter the element to insert
99
12 56 67 78 99 
1.Insert in tree 2.Search element 3.Exit
1
Enter the element to insert
54
12 54 56 67 78 99 
1.Insert in tree 2.Search element 3.Exit
1
Enter the element to insert
23
12 23 54 56 67 78 99 
1.Insert in tree 2.Search element 3.Exit
2
Enter the element to search
12
12 is Found

1.Insert in tree 2.Search element 3.Exit
2
Enter the element to search
99
99 is Found

1.Insert in tree 2.Search element 3.Exit
2
Enter the element to search
1
1 is Not Found

1.Insert in tree 2.Search element 3.Exit
3
BUILD SUCCESSFUL (total time: 55 seconds)
