import java.lang.*;
import java.io.*;

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


    boolean add(Comparable o) { 
	if (root == null) {
	    root = new BinaryTreeNode(o, null, null);
	    return true;
	}
	else
	    return addRecursive(o, root);
    }

    boolean contains(Comparable o) {
	return containsRecursive(o, root);
    }

    void inorder() {
	inorderRecursive(root);
    }
    

    boolean addRecursive(Comparable o, BinaryTreeNode node) { 
	int comparison = o.compareTo(node.content);

	if (comparison == 0)
	    return false;
	else if (comparison < 0) {
	    if (node.left == null) {
		node.left = new BinaryTreeNode(o, null, null);
		return true;
	    }
	    else
		return addRecursive(o, node.left);
	}
	else {
	    if (node.right == null) {
		node.right = new BinaryTreeNode(o, null, null);
		return true;
	    }
	    else
		return addRecursive(o, node.right);
	}
    }

    boolean containsRecursive(Comparable o, BinaryTreeNode node) {
	// IMPLEMENT THIS
    }
    

    void inorderRecursive(BinaryTreeNode node) {
	// IMPLEMENT THIS
    }
   

    public static void main(String[] args) {

	BinarySearchTree t = new BinarySearchTree();
	t.add( new Integer(10) );
	t.add( new Integer(20) );
	t.add( new Integer(1) );
	t.add( new Integer(3) );
	t.add( new Integer(2) );
	t.add( new Integer(15) );
	t.add( new Integer(22) );
	t.add( new Integer(24) );

	t.inorder();

	System.out.println("contains(2)  = " + t.contains(2));
	System.out.println("contains(15) = " + t.contains(15));
	System.out.println("contains(18) = " + t.contains(18));
	System.out.println("contains(22) = " + t.contains(22));

    }


    BinaryTreeNode root;
}