//Mason Marnell
//

class BinaryTree {
    Node root;
    public BinaryTree(String info)
    {
        root = new Node();
        root.info = info;
        root.left = null;
        root.right = null;
    }
    
    public void Add(String info)
    {
        Node currentnode = root;
        
        while(true)
        {
            if(currentnode.info.compareTo(info) > 0) // go left
            {
                if(currentnode.left != null)
                {
                    currentnode = currentnode.left;
                    continue;
                }
                else
                {
                    currentnode.left = new Node();
                    currentnode = currentnode.left;
                    currentnode.info = info;
                    break;
                }
                
            }
            else
            {
                if(currentnode.right != null)
                {
                    currentnode = currentnode.right;
                    continue;
                }
                else
                {
                    currentnode.right = new Node();
                    currentnode = currentnode.right;
                    currentnode.info = info;
                    break;
                }
            }
        }
    }
     public void insert(String data)
     {
         root = insert(root, data);
     }
     /* Function to insert data recursively */
     private Node insert(Node node, String data)
     {
         if (node == null)
             node = new Node(data);
         else
         {
             if(node.info.compareTo(data)>0)
                 node.left = insert(node.left,data);
             else
                 node.right = insert(node.right, data);
                          
         }
         return node;
     } 
    
     public void inorder()
     {
         inorder(root);
     }
     private void inorder(Node r)
     {
         if (r != null)
         {
             inorder(r.left);
             System.out.print(r.info +" ");
             inorder(r.right);
         }
     }

     public void reverseorder()
     {
         reverseorder(root);
     }
     private void reverseorder(Node r)
     {
         if (r != null)
         {
             inorder(r.right);
             System.out.print(r.info +" ");
             inorder(r.left);
         }
     }
     
     public void PreOrder()
     {
         PreOrder(root);
     }
     private void PreOrder(Node r)
     {
         if (r != null)
         {
        	 System.out.print(r.info +" ");
        	 inorder(r.left);
        	 inorder(r.right);
         }
     }
     public void PosOrder()
     {
         PosOrder(root);
     }
     private void PosOrder(Node r)
     {
         if (r != null)
         {
             inorder(r.left);
             inorder(r.right);
             System.out.print(r.info +" ");
         }
     }
}