/* Binary Tree */

public abstract class BinaryTree {
  public abstract BinaryTree makeEmpty( );
  public abstract BinaryTree leftChild( );
  public abstract BinaryTree rightChild( );
  public abstract Object     getItem( );
  public abstract boolean    isLeaf( );
  public abstract int        height( );
  public abstract BinaryTree duplicate( );
  public abstract String     toString( );
  public abstract BinaryTree merge( Object root, BinaryTree t );
  public abstract void       preorder( );
  public abstract void       postorder( );
  public abstract void       inorder( );
}


class Empty extends BinaryTree {
  public BinaryTree makeEmpty( )    { return new Empty(); }
  public BinaryTree leftChild( )    { return null; }
  public BinaryTree rightChild( )   { return null; }
  public Object     getItem( )      { return null; }
  public boolean    isLeaf( )       { return true; }
  public int        height( )       { return -1; }
  public BinaryTree duplicate( )    { return new Empty(); }
  public String     toString( )     { return " "; }
  public BinaryTree merge( Object root, BinaryTree t ) {
    return new Node( root, new Empty(), t );
  }
  public void       preorder( )     { return; }
  public void       postorder( )    { return; }
  public void       inorder( )      { return; }
}


class Node extends BinaryTree {
  Object     item;
  BinaryTree left;
  BinaryTree right;
  
  public Node( )                    { this( null ); }
  
  public Node( Object item )        { this( item, new Empty(), new Empty() ); }
  
  public Node( Object item, BinaryTree left, BinaryTree right ) {
    this.item  = item;
    this.left  = left;
    this.right = right;
  }
  
  public BinaryTree makeEmpty( )    { return new Empty(); }
  public BinaryTree leftChild( )    { return left; }
  public BinaryTree rightChild( )   { return right; }
  public Object     getItem( )      { return item; }
  public boolean    isLeaf( ) {
    return ( left instanceof Empty ) && ( right instanceof Empty );
  }
  public int        height( ) {
    return 1 + Math.max( left.height( ), right.height( ) );
  }
  public BinaryTree duplicate( ) {
    return new Node( item, left.duplicate( ), right.duplicate( ) );
  }
  public String     toString( ) {
    return item + " [ " + left.toString() + "," + right.toString() + " ] "; 
  }
  public BinaryTree merge( Object root, BinaryTree t ) {
    if( this == t ) {  return this; }  // merging the same tree?  Don't think so...
    return new Node( root, this, t );
  }
  public void       preorder( ) {
    // Do something with your item.  For example, print it out
    System.out.println( item );
    left.preorder( );
    right.preorder( );
  }
  public void       postorder( ) {
    left.postorder( );
    right.postorder( );
    System.out.println( item );
  }
  public void       inorder( ) {
    left.inorder( );
    System.out.println( item );
    right.inorder( );
  }
}