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 the first n 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 contains(myRoot, i); 
    }



    // Return true iff the tree rooted at `root' contains i.

    private static boolean contains(BinaryIntNode root, int i){
        if (root == null)
	    // The tree is empty, so it certainly doesn't contain i.
	    return false;
	else if (root.key == i)
	    // i occurs at the root.
	    return true;
	else 
	    // i is not at the root.  See if it's contained in either subtree.
	    return contains(root.left, i) || contains(root.right, i);
	    
    }



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

    public int numOccurrences(int num){
        return numOccurrences(num, myRoot);
    }



    // Return the number of times num occurs in the tree rooted at `root'.

    private static int numOccurrences(int num, BinaryIntNode root){ 
        if (root == null)
	    // The tree is empty, so it has no occurrences of num.
	    return 0;
	else if (root.key == num)
	    // The root contains num, so add that occurrence to the number of
	    // occurrences in the subtrees.
	    return 1 + numOccurrences(num, root.left) + 
	               numOccurrences(num, root.right);
        else
	    // The root doesn't contain num, so just return the number of
	    // occurrences in the subtrees.
	    return numOccurrences(num, root.left) + 
	           numOccurrences(num, root.right);
    }



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

    public int biggest(){
       return biggest(myRoot);
    }



    // Return the biggest integer in the tree rooted at `root'.
    // Precondition: root is not null.

    private static int biggest(BinaryIntNode root){

	if (root.left == null && root.right == null){
	    // The root is a leaf; it itself is the biggest in the tree.
	    return root.key;
	} else if (root.left == null){
	    // The root has only a right child.  Look there in case its
	    // biggest is bigger than the root.
	    return Math.max(root.key, biggest(root.right));
	} else if (root.right == null){
	    // The root has only a left child.  Look there in case its
	    // biggest is bigger than the root.
	    return Math.max(root.key, biggest(root.left));
	} else {
	    // The root has two children.  Look on both sides.
	    return Math.max ( Math.max(biggest(root.left), biggest(root.right)),
	                      root.key
			    );
        }
    }



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

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


     
    // Replace every occurrence of old in the tree rooted at `root', 
    // with replacement.

    public static void replace(BinaryIntNode root, 
                                        int old, int replacement){
        if (root != null) {
	    // There is at least a root.  Replace its key, if appropriate.
	    if (root.key == old){
	        root.key = replacement;
            }
	    // Now make any necessary replacements in the subtrees.
	    replace(root.left, old, replacement);
	    replace(root.right, old, replacement);
	}
    }



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

    public void flip(){
        flip(myRoot);
    }



    // Flip the tree rooted at `root'.  That is, for each node in it, swap 
    // that node's left and right child.

    private static void flip(BinaryIntNode root){
        if (root != null) {
	    // The tree is not empty, so there is work to do.
	    // Flip the subtrees themselves.
	    flip(root.left);
	    flip(root.right);
	    // Now swap the left and right subtrees.
	    BinaryIntNode temp = root.left;
	    root.left = root.right;
	    root.right = temp;
	}
    }



    // 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;
    }
}