public class BTree {

    Node root;

    public BTree(){root = null;}

    //
    // A BTree is a root node, possibly empty. See Node.java
    // for details of a Node

    public boolean isEmpty(){return root==null;}
    //
    // Is the BTree empty?
    //

    public Node getRoot(){return root;}
    //
    // Deliver the Node that is the root of the BTree
    //

    public void add(int e){
	if (isEmpty())
	    root = new Node(e);
	else 
	    add(e,root);
    }
    //
    // Add the integer e into the BTree if it is not
    // already there! Note the call to add(e,root) and it's
    // definition below. 
    //
    // NOTE: the BTree is ordered, such that for any Node x
    //       x.getLeft().getData() < x.getData() and
    //       x.getData() < x.getRight().getData()
    //
    // HINT: You might want to use add(e) and add(e,x) as templates 
    //       for other methods
    // 

    private void add(int e,Node x){
	if (x.getLeft()==null && e<x.getData())        // (1)
	    x.setLeft(new Node(e));                    // (2)
	else if (x.getRight()==null && e>x.getData())  // (3)
	    x.setRight(new Node(e));                   // (4)
	else if (e<x.getData())                        // (5)
	    add(e,x.getLeft());                        // (6)
	else if (e>x.getData())                        // (7)
	    add(e,x.getRight());                       // (8)
    }
    //
    // Add the integer e into the binary tree of Nodes rooted at
    // Node x. 
    // (1) if the current node x has an empty left and e is
    //     less than the data in x, set the left of x to be 
    //     a new leaf Node with e as data
    // (3) if node x has an empty right and e is greater than
    //     the data in x, set right of x to be a new leaf Node
    //     with e as data
    // (5) e is less than data in x AND left is not empty, so ...
    // (6) go do the addition of e into the left subtree! This
    //     is done via the recursive call add(e,x.getleft())
    // (7) e is greater than the data in x AND right is not empty, so ...
    // (8) go do the addition of e into the right subtree! This
    //     is done via the recursive call add(e,x.getRight())
    //

    public String toString(){return toString(root);}

    private String toString(Node n){
	if (n==null)
	    return "*";
	else 
	    return "(" + 
		    toString(n.getLeft()) + 
		    n.getData() + 
		    toString(n.getRight()) +
		   ")";
    }
    //
    // A Btree looks like this ...
    // (0) If it is empty we print *
    // (1) A leaf Node with data, say data = 5, is printed as (*5*)
    //     That is, it has no left and no right subtree 
    // (2) A node with data 5, and a left subtree with one leaf Node with
    //     data = 3 and a right subtree with one leaf node with data = 7
    //    is printed as ((*3*)5(*7*))
    //

    //
    // Define the methods below. See the Readme file for more info
    // and the file trace
    //

    public int size(){return Integer.MIN_VALUE;}
    // 
    // Delivers the number of Nodes in the BTree
    //

    public int sum(){return Integer.MIN_VALUE;}
    //
    // Delivers the accumulation of the data in the tree
    //

    public int max(){return Integer.MIN_VALUE;}
    //
    // Delivers the largest data in the BTree.
    // If the BTree is empty deliver the smallest
    // integer value Integer.MIN_VALUE
    //
    // NOTE: the BTree is ordered and this should be exploited
    //       i.e. the entire BTree need not be explored!
    //

    public boolean isPresent(int e){return false;}	
    //
    // Delivers true if there is a Node in the BTree
    // with data == e, false otherwise.
    //
    // NOTE: the BTree is ordered and this should be exploited
    //       i.e. the entire BTree need not be explored!
    //

    public int height(){return Integer.MIN_VALUE;}
    //
    // Return the (integer) height of the BTree. If the
    // BTree is empty deliver Integer.MIN_VALUE
    //

}