import java.util.*;
 
public class ThreadedTree<E extends Comparable<E>>
{
  private ThreadedTreeNode<E> root;
  private ThreadedTreeNode<E> trailer;
  private ThreadedTreeNode<E> current;
        
  public ThreadedTree()
  {
      root = null;
  }
 
  public E findMin()
  {
        current = root;
      while(current.getLeft() !=null)
      {
          current = current.getLeft();
      }
      return current.getData();
  }
 
  public E findMax()
  {
      while(current.getRight() != null)
      {
          current = current.getRight();
      }
      return current.getData();
  }
 
  public void makeEmpty()
  {
      root = null;
  }
 
  public boolean isEmpty()
  {
      if(root==null)
          return true;
      else
          return false;
  }
 
        public void insertThreaded(E x)
        {
                if (root==null)
                {
                        root = new ThreadedTreeNode<E>(x);
                        return;
                }
                current = root;
                //
                //find appropriate null node to insert new node
                while(current != null)
                {
                        //initialize trailer to current
                        trailer = current;
                        //if x > current.data, move to right subtree
                        if (x.compareTo(current.getData())>0)
                        {
                                trailer = current;
                                current = current.getRight();
                        }
                        //if x < current.data, move to left subtree
                        else if (x.compareTo(current.getData())<0)
                        {
                                trailer = current;
                                current = current.getLeft();
                        }
                        //break loop if node x already exist in tree.
                        else
                        {
                                return;
                        }
                }
                //
                //current is null, compare x with trailer.data and insert x as child to trailer.
                //if x > trailer.data, move to right subtree
                if (x.compareTo(trailer.getData())>0)
                {
                        //create new node for x with null left reference and right thread from trailer
                        ThreadedTreeNode<E> node = new ThreadedTreeNode<E>(x, null, trailer.getRight());
                        //set trailer right reference to x
                        trailer.setRight(node);
                        //remove isThread flag from trailer
                        trailer.setIsThread(false);
                        
                }
                //if x < trailer.data, move to left subtree
                else if(x.compareTo(trailer.getData())<0)
                {
                        //create new node for x with null left reference and right thread from trailer
                        ThreadedTreeNode<E> node = new ThreadedTreeNode<E>(x, null, trailer);
                        node.setIsThread(true);
						//set trailer left reference to x
						
                        trailer.setLeft(node);
                        //remove isThread flag from trailer
                        trailer.setIsThread(false);
                }
                //do nothing if node x already exists in tree
                else
                {       
                return;
                }
        }
        
        public void inorderThreadedPrint()
        {
                current = root;
                while(current.getLeft() != null)
                {
                        current = current.getLeft();
                }
                do
                {
                        if(current.getIsThread()==true)
                        {
                                System.out.println(current.getData());
                                current = current.getRight();
                        }
                        else if(current.getIsThread()==false)
                        {
                                System.out.println(current.getData());
                                current = current.getRight();
                                while(current.getLeft() != null)
                                {
                                        current = current.getLeft();
                                }
                        }
                        
                } while(current!=null);
                
        }
        
        public void levelThreadedPrint()
        {
        }
 
}