import java.util.*;
public class BST{
    int data;
    BST left, right;
    BST(int x){
        this.left=this.right=null; data=x;
    }
    public void insert(int i){
        if(i<=data){
            if(left!=null)
            right.insert(i);
            else
            left = new BST(i);

        }
        else if (i>=data){
            if (right!=null)
            right.insert(i);
            else right = new BST(i);

        }
    }
    public void inOrder(BST tree){
        if(tree!=null){
            inOrder(tree.left);
            System.out.print(tree.data+" ");
            inOrder(tree.right);
        }
    }
    public void preOrder(BST tree){
        if (tree!= null){
            System.out.print(tree.data+" ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }
    public void postOrder(BST tree){
        if (tree!=null){
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.print(tree.data+" ");

        }
    }
    public void BFS(BST tree){ // Printing Breadth-First
       System.out.print(tree.data);

    }
    public static void main(String args[]){
        char cho; int n;
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the root node ");
        n=sc.nextInt();
        BST ob = new BST(n);
        System.out.print("enter ur choice y or n =  ");
        cho =sc.next().charAt(0);
        while(cho == 'y'){
            System.out.print("enter node value");
            n =sc.nextInt();
            ob.insert(n);
            System.out.print("enter ur choice y or n ");
            cho =sc.next().charAt(0);
        }
        System.out.print("inorder traversal");
        ob.inOrder(ob);
        System.out.print("preorder traversal");
        ob.preOrder(ob);
        System.out.print("inorder traversal");
        ob.postOrder(ob);

    }
}