class BinaryTreeNode {
    int element;
    BinaryTreeNode left;
    BinaryTreeNode right;
    int size;
    public BinaryTreeNode(int theElement) {
	element = theElement;
        left = null;
        right = null;
        size = 1;
    }
}

class BinarySearchTree {
    BinaryTreeNode root;

    public BinarySearchTree(){
	root = null;
    }

    public boolean search(int theElement) 
    {
	BinaryTreeNode x = root;
        while (x != null) {
	    if (x.element == theElement) return true;
            if (x.element < theElement) x = x.right;
            else x = x.left;
	}
        return false;
    }

    public void insert(int theElement)
    { 
        if (search(theElement)) return;

        if (root == null) {
	    root = new BinaryTreeNode(theElement);
            return;
	}
	BinaryTreeNode x = root;
        boolean done = false;
        while (! done) {
            x.size = x.size + 1;
	    if (x.element == theElement) return;
            if (x.element < theElement) {
		if (x.right == null) 
		    {
			x.right = new BinaryTreeNode(theElement);
                        done = true;
                    }
		else 
                    { x = x.right; }
	    }
	    else {
                if (x.left == null) {
		    x.left = new BinaryTreeNode(theElement);
                    done = true;
		}
                else
                    { x = x.left;}
            }
	} 
    }

    public void printTree(){
	print(root);
    }

    public void print(BinaryTreeNode x) {
	if (x != null) {
	    print(x.left);
            System.out.println(x.element + " : " + x.size);
            print(x.right);
        }
    }
}

class BSTEnhanced {
    public static void main(String [] args) {
	BinarySearchTree myTree = new BinarySearchTree();
        int e;

        for (int i = 0; i < 10; i++) {
	    e = (int) (20 * Math.random());
            myTree.insert(e);
            System.out.println(e);
	}


        myTree.printTree();
    }
}