import java.util.ArrayList;

public class BinarySearchTree {
    public static Node root;

    public static ArrayList<Integer> arrayList;

    public BinarySearchTree(){
        this.root = null;
    }

    public void savePreOrder(Node root){
        if(root == null) return ;

        arrayList.add(root.data);

        savePreOrder(root.left);
        savePreOrder(root.right);
    }

    public void insert(int number){
        Node newNode = new Node(number);

        if(root == null){
            root = newNode;
            return ;
        }

        Node current = root;
        Node parent = null;

        while(true){
            parent = current;
            if(number < current.data){
                current = current.left;
                if(current == null){
                    parent.left = newNode;
                    return ;
                }
            } else {
                current = current.right;
                if(current == null){
                    parent.right = newNode;
                    return ;
                }
            }
        }
    }

    public static void main(String[] args){
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(25);
        bst.insert(15);
        bst.insert(50);
        bst.insert(22);
        bst.insert(70);
        bst.insert(35);
        bst.insert(10);
        bst.savePreOrder(bst.root);
        for(int i = 0; i < arrayList.size(); i++) {
            System.out.println(arrayList.get(i));
        }
    }
}