import java.util.StringTokenizer;

class LinkedBinaryIntTree implements BinaryIntTree {

    // My root.
    private BinaryIntNode myRoot;

    // Representation Invariant:
    // myRoot is either null (in which case I am empty) or refers to a node
    // that is the myRoot of a well-formed binary tree.



    // Return whether or not I am empty.

    public boolean empty(){
        return (myRoot==null);
    }



    // Make me contain all the integers in st.
    // If I already contain anything, that is lost.
    // If n is less than 1, I will be made empty.
    // Precondition: n is <= the number of integers in st.

    public void build(StringTokenizer st, int n){
       myRoot = buildTree(st, n);
    }



    // Return a BinaryIntNode that is the root of a tree containing
    // the first n integers in st.
    // If n is less than 1, return null.
    // Precondition: n <= the number of integers in st.

    private BinaryIntNode buildTree(StringTokenizer st, int n){
	if (n < 1)
	    return null;
	else {
            int half = (n-1)/2;
            int remainder = (n-1) - half;
 
            BinaryIntNode leftSubtree = buildTree(st, half);
            // Build a node and put the next integer from the
            // StringTokenizer into it.
            BinaryIntNode node = new BinaryIntNode();
            node.key = (new Integer( st.nextToken() )).intValue();
            BinaryIntNode rightSubtree = buildTree(st, remainder);
 
            node.left = leftSubtree;
            node.right = rightSubtree;
            return node;
	}
    }
    
 

    // Return true iff I contain i.

    public boolean contains(int i){
        return false;
    }



    // Return the number of times num occurs in me.

    public int numOccurrences(int num){
        return 0;
    }


     
    // Return the biggest integer in me.
    // Precondition: I am not empty.

    public int biggest(){
       return 99;
    }



    // Replace every occurrence of old in my tree, with replacement.

    public void replace(int old, int replacement){
    }


     
    // Flip me.  That is, for each node in me, swaps that node's left and
    // right child.

    public void flip(){
    }



    // Return a (possibly multi-line) string that nicely represents my 
    // contents and structure.  Indentation is used to help show my structure.

    public String toString(){
        return toString(myRoot, 0);
    }



    // Return a (possibly multi-line) string that nicely represents the
    // contents and structure of the tree whose root is `root'.
    // The whole string should be indented `indentation' spaces.

    private static String toString(BinaryIntNode root, int indentation){
	if (root == null)
	    return "";
	else {
            String answer = "";
	    answer += toString(root.right, indentation+5);
	    answer += pad(indentation) + root.key + "\n";
	    answer += toString(root.left, indentation+5);
	    return answer;
        }
    }



    // Return a string of n blanks, or the empty string if n <= 0.
    // (There may be a better way to do using the Java API, but I haven't
    // found it.)

    private static String pad(int n){
	String answer = "";
        for (int i=1; i<= n; i++){
	    answer += " ";
	}
	return answer;
    }



    public static void main(String[] args){
        // This just shows you how to build a tree and print a tree.
        StringTokenizer input = 
              new StringTokenizer("1 2 3 4 5 6 7 8 9 10 11 12 13 14 15");
	LinkedBinaryIntTree t = new LinkedBinaryIntTree();
	t.build(input, 15);
	System.out.println("Initial tree:\n" + t);
    }
}