import java.util.Iterator;
import java.util.Stack;
import java.util.NoSuchElementException;

public class BinaryTree<T> implements Iterable<T> {
    private BinaryTreeNode<T> root;
    
    /**
     * Default constructor
     */
    public BinaryTree() {
        root = null;
    } // end constructor
    /**
     * Root constructor
     * @param rootData data assigned to the root
     */
    public BinaryTree(T rootData) {
        root = new BinaryTreeNode<T>(rootData);
    }
    /**
     * Constructor from two Binary Trees
     * @param rootData data assigned to the root
     * @param left the left subtree
     * @param right the right subtree
     */
    public BinaryTree(T rootData, BinaryTree<T> left, BinaryTree<T> right) throws Exception {
        if( left.root == right.root && left.root != null) throw new Exception("Bad Construction");
        root = new BinaryTreeNode<T>(rootData,left.root,right.root);
    }
    
    /**
     * Check for empty tree
     * @return true if this tree is empty; false otherwise
     */
    public boolean isEmpty() {
        return root == null;
    } // end isEmpty
    /**
     * Accessor for the root data
     * @return root data
     */
    public T getData() {
        return root.data;
    }
    /**
     * Modifier for the root data
     * @param x is the new root data
     */
    public void setData(T x) {
        root.data = x;
    }
    
    private BinaryTree(BinaryTreeNode<T> treeNode) {
        root = treeNode;
    }
    /**
     * Accessor for the left subtree
     * @return left subtree
     */
    public BinaryTree<T> left() {
        return new BinaryTree<T>(root.left);
    }
    /**
     * Accessor for the right subtree
     * @return right subtree
     */
    public BinaryTree<T> right() {
        return new BinaryTree<T>(root.right);
    }
    /**
     * Check for a leaf
     * @ return true if a leaf; false otherwise
     */
    public boolean isLeaf() {
        return root.isLeaf();
    }
    /**
     * Make the tree empty
     */
    public void makeEmpty() {
        root = null;
    }
    /**
     * return a String representation of the nodes in the tree
     * @return a String representation of the nodes in preorder
     */
    public String toString() {
        return toString(root);
    }
    
    private String toString(BinaryTreeNode<T> treeNode) {
        String out = "";
        if( treeNode == null ) return out;
        out += treeNode.data.toString() + " ";
        out += toString(treeNode.left);
        out += toString(treeNode.right);
        return out;
    } // end toString
    /**
     * return the infix String representation of the nodes in the tree
     * @return the infix String representation of the nodes in preorder
     */
    public String toInFixString() {
        return toInFixString(root);
    }
    
    private String toInFixString(BinaryTreeNode<T> treeNode) {
        String out = "";
        if( treeNode == null ) return out;
        out += toInFixString(treeNode.left);
        out += treeNode.data.toString() + " ";
        out += toInFixString(treeNode.right);
        return out;
    } // end toInFixString
    
    /**
     * return the postfix String representation of the nodes in the tree
     * @return the postfix String representation of the nodes in preorder
     */
    public String toPostFixString() {
        return toPostFixString(root);
    }
    
    private String toPostFixString(BinaryTreeNode<T> treeNode) {
        String out = "";
        if( treeNode == null ) return out;
        out += toPostFixString(treeNode.left);
        out += toPostFixString(treeNode.right);
        out += treeNode.data.toString() + " ";
        return out;
    } // end toPostFixString
    
    /**
     * return the prefix String representation of the nodes in the tree
     * @return the prefix String representation of the nodes in preorder
     */
    public String toPreFixString() {
        return toPreFixString(root);
    }
    
    private String toPreFixString(BinaryTreeNode<T> treeNode) {
        String out = "";
        if( treeNode == null ) return out;
        out += treeNode.data.toString() + " ";
        out += toPreFixString(treeNode.left);
        out += toPreFixString(treeNode.right);
        return out;
    } // end toPreFixString
    
    
    public Iterator<T> iterator() {
        return new InorderIterator<T>(root);
    } // end inorderIterator
    
    
    private class InorderIterator<T> implements Iterator<T> {
        BinaryTreeNode<T> current;
        Stack<BinaryTreeNode<T>> stack;
        
        private InorderIterator(BinaryTreeNode<T> root) {
            current = root;
            stack = new Stack<BinaryTreeNode<T>>();
            stack.push(null);
            current = goLeft(current,stack);
        }// end construcor
        
        private BinaryTreeNode<T> goLeft(BinaryTreeNode<T> current,Stack<BinaryTreeNode<T>> stack) {
            if( current == null ) return null;
            while( current.left != null ) {
                stack.push(current);
                current = current.left;
            } // end while
            return current;
        } // end goLeft
        
        public boolean hasNext() {
            return current != null;
        } // end hasNext
        
        public T next() {
            if( !hasNext() ) throw new NoSuchElementException();
            BinaryTreeNode<T> save = current;
            if( current.right != null ) {
                current = goLeft(current.right,stack);
            } else {
                current = stack.pop();
            } // end if
            return save.data;
        } // end next
        
        public void remove() {
            throw new UnsupportedOperationException();
        }
        
    } // end InorderIterator
    
    public Iterator<T> preorderIterator() {
        return new PreorderIterator<T>(root);
    } // end preorderIterator
    
    
    private class PreorderIterator<T> implements Iterator<T> {
        Stack<BinaryTreeNode<T>> stack;
        
        private PreorderIterator(BinaryTreeNode<T> root) {
            stack = new Stack<BinaryTreeNode<T>>();
            if( root != null ) stack.push(root);
        }
        
        public boolean hasNext() {
            return !stack.isEmpty();
        } // end hasNext
        
        private BinaryTreeNode<T> nextNode() {
            if( !hasNext() ) throw new NoSuchElementException();
            BinaryTreeNode<T> next = stack.pop();
            if( next.right != null ) stack.push(next.right);
            if( next.left != null ) stack.push(next.left);
            return next;
        } // end nextNode
        
        public T next() {
            return nextNode().data;
        } // end next
        
        public void remove() {
            throw new UnsupportedOperationException();
        }
        
    } // end PreorderIterator<T>
    
    public Iterator<T> postorderIterator() {
        return new PostorderIterator<T>(root);
    } // end preorderIterator
    
    
    private class PostorderIterator<T> implements Iterator<T> {
        Stack<BinaryTreeNode<T>> stack;
        Stack<T> dataStack;
        
        private PostorderIterator(BinaryTreeNode<T> root) {
            stack = new Stack<BinaryTreeNode<T>>();
            dataStack = new Stack<T>();
            if( root != null ) stack.push(root);
            while( !stack.isEmpty() ) {
                BinaryTreeNode<T> next = stack.pop();
                if( next.left != null ) stack.push(next.left);
                if( next.right != null ) stack.push(next.right);
                dataStack.push(next.data);
            }// end while
        }
        
        public boolean hasNext() {
            return !dataStack.isEmpty();
        } // end hasNext
        
        public T next() {
            if( !hasNext() ) throw new NoSuchElementException();
            return dataStack.pop();
        }
        
        public void remove() {
            throw new UnsupportedOperationException();
        }
        
    } // end PostorderIterator<T>
    
    private static class BinaryTreeNode<T> {
        T data;
        BinaryTreeNode<T> left;
        BinaryTreeNode<T> right;
        public BinaryTreeNode() {}
        public BinaryTreeNode(T item) {
            data = item;
            right = null;
            left = null;
        } // constructor
        public BinaryTreeNode(T item,BinaryTreeNode<T> left,BinaryTreeNode<T> right) {
            data = item;
            this.left = left;
            this.right = right;
        } // end constructor
        private boolean isLeaf() {
            return left == null && right == null;
        }
        public String toString() {
            return data + "";
        } // end toString
    } // end BinaryTreeNode<E>
    
} // end BinaryTree<T>