// COMP102
// Example 15: Binary Trees
//
// Paul E. Dunne 1/12/99
//
public class BinaryTree
  {
  protected Object Root;                 // Tree Root
  protected BinaryTree Left;             // Pointer to Left Sub-tree
  protected BinaryTree Right;            // Pointer to Right Sub-tree
  //*****************************************************
  // Binary Tree Methods                                *
  //*****************************************************
  //
  // Test is this tree contains no nodes
  //
  public boolean IsEmpty()
    {
    return (Root==null)&&(Left==null)&&(Right==null);
    }
  //*****************************************************
  // Set and Obtain the Root of this Binary Tree        *
  //*****************************************************
  public void SetRoot( Object root_val )
    {
    Root = root_val;
    }
  public Object GetRoot ()
    {
    return Root;
    }
  //*****************************************************
  // Set the Left/Right Subtress of this BinaryTree     *
  //*****************************************************
  public void SetLeft( BinaryTree L )
    {
    Left=L;
    }
  //
  public void SetRight( BinaryTree R )
    {
    Right=R;
    }
  //*****************************************************
  // Get the Left/Right Subtrees of this BinaryTree     *
  //*****************************************************
  public BinaryTree GetLeft ()
    {
    return Left;
    }
  //
  public BinaryTree GetRight()
    {
    return Right;
    }
 //*******************************************************//
 // Calculate the number of nodes in a given Binary Tree. //
 //*******************************************************//
 public static int SizeOf( BinaryTree T )
   {
   if (T.IsEmpty())
     return 0;
   else
     return 1 + SizeOf(T.GetLeft()) + SizeOf(T.GetRight());
   }
 //*******************************************************//
 // Calculate the number of Leaves in a given Binary Tree //
 //*******************************************************//
 public static int NumLeaves (BinaryTree T)
   {
   if (SizeOf(T) <= 1)
     return SizeOf(T);
   else
     return NumLeaves(T.GetLeft()) + NumLeaves(T.GetRight());
   }
 public static int DepthOf (BinaryTree T)
   {
   if (SizeOf(T) <= 1)
     return SizeOf(T);
   else
     return 1+Math.max( DepthOf(T.GetLeft()), DepthOf(T.GetRight()) );
   }
 //*******************************************************//
 // Compare the given key with the root of this Binary    //
 // Tree, using a numeric comparison if both are Number   //
 // instances, and String comparison otherwise.           //
 // Returns true of Key is `less than' Root               //
 //*******************************************************//
 public boolean IsBeforeRoot ( Object Key )
    {
    double xv, yv;
    if (IsEmpty())
      return false;
    else 
      {
      if ( (Key  instanceof Number) && 
           (Root instanceof Number) )
        {
        xv = Double.valueOf(Key.toString()).doubleValue();
        yv = Double.valueOf(Root.toString()).doubleValue();
        return (xv<yv);
        }
      else
        return ( (Key.toString()).compareTo(Root.toString()) < 0);
      };
    }
 //*******************************************************//
 // Similarly, comparison method that returns true if    *//
 // the given Key is 'greater than' the Root.            *//
 //*******************************************************//
 public boolean IsAfterRoot ( Object Key )
    {
    double xv, yv;
    if (IsEmpty())
      return false;
    else 
      {
      if ( (Key instanceof Number) && 
         (Root instanceof Number) )
        {
        xv = Double.valueOf(Key.toString()).doubleValue();
        yv = Double.valueOf(Root.toString()).doubleValue();
        return (xv>yv);
        }
      else
        return ( (Key.toString()).compareTo(Root.toString()) > 0);
      };
    }
 //*******************************************************//
 // Insert a new Object into this tree, maintaining a    *//
 // Sorted ordering                                      *//
 //*******************************************************//
 public void Insert(Object Key)
    {
    if (IsEmpty())
      {
      Root = Key;
      Left = new BinaryTree();
      Right = new BinaryTree();
      }
    else
      {
      if ( IsBeforeRoot(Key) )
        {
        Left.Insert(Key);
        }
      else if ( IsAfterRoot(Key) )
        {
        Right.Insert(Key);
        };
      };
    }
  }