Stuff

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.getRight());
			//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()
	{
	}

}