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


public class Tree implements Iterable<Integer>{
   private Node root;
   
   public Tree(){
     root = Leaf.getLeafInstance();
   }
   public Tree(Node root){
     this.root=root;
   } 
   public Node getRoot() {
    return root;
  }
  public void setRoot(Node root) {
    this.root = root;
  }
  public void add(int x){
     root = root.add(x);
   }
   @Override public String toString(){
     return root.toString();
   }
   public Pair<Tree> cut(int key){
     Pair<Node> pair = root.cut(key);
     return new Pair<Tree>(new Tree(pair.getFirst()),new Tree(pair.getSecond()));
   }
   public List<Integer> toList(){
     return root.toList();
   }
   public Iterator<Integer> iterator(){
     return new DepthFirstIterator();
   }
   public class DepthFirstIterator implements Iterator<Integer> {
    Stack<InternalNode> stack;
    
    public DepthFirstIterator(){
      stack=  new Stack<InternalNode>();
      if (root instanceof InternalNode) stack.push((InternalNode)root);
    }
    
    public boolean hasNext() {
      return stack.size() !=0;
    }

    public Integer next() {
      if (! hasNext()) throw new NoSuchElementException();
      InternalNode node = stack.pop();
      if (node.getRight() instanceof InternalNode) stack.push((InternalNode)node.getRight());
      if (node.getLeft() instanceof InternalNode) stack.push((InternalNode)node.getLeft());
      return node.getKey();
    }

    public void remove() {
      throw new UnsupportedOperationException();
    }
   }
}