package lab06;
import java.util.*;
 
class BTreeNode<T> {
    T element;
    BTreeNode<T> leftChild, rightChild;
    BTreeNode( T element, BTreeNode<T> leftChild, BTreeNode<T> rightChild ){
        this.element = element;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
    T getElement(){ return element; }
    BTreeNode<T> getLeft(){ return leftChild; }
    BTreeNode<T> getRight(){ return rightChild; }
}
 
class LevelorderIterator<T> implements Iterator<T>{
    // We will use the LinkedList implementation for our Queue
    LinkedList<BTreeNode<T>> iteratorQueue;
    
    LevelorderIterator(BTreeNode<T> root){
        iteratorQueue = new LinkedList<BTreeNode<T>>();
        iteratorQueue.add(root);
    }
    public boolean hasNext() {
        return !iteratorQueue.isEmpty();
    }    
    public T next() {
        // Remove current node from the queue.
        BTreeNode<T> curNode = iteratorQueue.remove();
                
        // Add the left child of curNode if present to the queue.
        if( curNode.getLeft() != null )
        	iteratorQueue.add(curNode.getLeft());
        
        // Add the right child of curNode if present to the queue.
        if( curNode.getRight() != null )
        	iteratorQueue.add(curNode.getRight());
        
        // Return the data (element) for curNode.
        return curNode.getElement();
    }
    public void remove() {}    
}
 
// StackElement has two fields: BTreeNode and a boolean visited,
// this class will be used in Inorder, Preorder and Postorder iterators below.  
class StackElement<T> {
    BTreeNode<T> btreeNode;
    boolean visited;
    StackElement( BTreeNode<T> btreeNode, boolean visited ){
        this.btreeNode = btreeNode;
        this.visited = visited;
    }
    BTreeNode<T> getNode(){    return btreeNode; }
    boolean isVisited(){ return visited; }
}
 
class InorderIterator<T> implements Iterator<T>{
    Stack<StackElement<T>> iteratorStack;
    
    InorderIterator(BTreeNode<T> root){
        iteratorStack = new Stack<StackElement<T>>();
        iteratorStack.push(new StackElement<T>(root, false));
    }
    public boolean hasNext() {        
        return !iteratorStack.isEmpty();
    }
    public T next() {
    
        // Repeat until we have a visited node on top of the stack.
        while( !iteratorStack.peek().isVisited() ){
        
            // Get current node from top of the stack.
        	BTreeNode<T> curNode = iteratorStack.pop().getNode(); 
            
            // If right child is present, push it on the stack as not-visited.
        	if( curNode.getRight() != null )
        		iteratorStack.push( new StackElement<T>(curNode.getRight(), false) );
            
            // Push current node on the stack as visited.
        	iteratorStack.push(new StackElement<T>(curNode, true));
            
            // If left child is present, push it on the stack as not-visited.
        	if( curNode.getLeft() != null )
        		iteratorStack.push(new StackElement<T>(curNode.getLeft(), false));
        }
        
        // Pop the node on top of the stack (this node is a visited node) 
        // and return its data.
        return iteratorStack.pop().getNode().getElement();
    }
    public void remove() {}
}
 
class PreorderIterator<T> implements Iterator<T>{
    Stack<StackElement<T>> iteratorStack;
    
    PreorderIterator(BTreeNode<T> root){
        iteratorStack = new Stack<StackElement<T>>();
        iteratorStack.push(new StackElement<T>(root, false));
    }
    public boolean hasNext() {        
        return !iteratorStack.isEmpty();
    }
    public T next() {
        while( !iteratorStack.peek().isVisited() ){
            BTreeNode<T> curNode = iteratorStack.pop().getNode();
            
            // TASK:
            // Fill in the code here for PreorderIterator.next() following 
            // the example for InorderIterator.next().
            
            // If right child is present, push it on the stack as not-visited.
        	if( curNode.getRight() != null )
        		iteratorStack.push( new StackElement<T>(curNode.getRight(), false) );
            
        	if( curNode.getLeft() != null )
        		iteratorStack.push( new StackElement<T>(curNode.getLeft(), false) );
        	
        	iteratorStack.push(new StackElement<T>(curNode, true));
        	
        }
        return iteratorStack.pop().getNode().getElement();
    }
    public void remove() {}
}
 
class PostorderIterator<T> implements Iterator<T>{
    Stack<StackElement<T>> iteratorStack;
    
    PostorderIterator(BTreeNode<T> root){
        iteratorStack = new Stack<StackElement<T>>();
        iteratorStack.push(new StackElement<T>(root, false));
    }
    public boolean hasNext() {        
        return !iteratorStack.isEmpty();
    }
    public T next() {
        while( !iteratorStack.peek().isVisited() ){
            BTreeNode<T> curNode = iteratorStack.pop().getNode();
            
            // TASK:
            // Fill in the code here for PostorderIterator.next() following 
            // the example for InorderIterator.next().
            
            iteratorStack.push(new StackElement<T>(curNode, true));
            
            if( curNode.getRight() != null )
        		iteratorStack.push( new StackElement<T>(curNode.getRight(), false) );
            
        	if( curNode.getLeft() != null )
        		iteratorStack.push( new StackElement<T>(curNode.getLeft(), false) );
            
        }
        return iteratorStack.pop().getNode().getElement();
    }
    public void remove() {}
}
 
public class BTree<T> {
    BTreeNode<T> root;    
    BTree(BTreeNode<T> root){
        this.root = root;
    }
    Iterator<T> getLevelOrderIterator(){
        return new LevelorderIterator<T>(root);
    }
    Iterator<T> getInOrderIterator(){
        return new InorderIterator<T>(root); 
    }
    Iterator<T> getPreOrderIterator(){
        return new PreorderIterator<T>(root); 
    }
    Iterator<T> getPostOrderIterator(){
        return new PostorderIterator<T>(root); 
    }
}