// Michael Tartaglia
// BINARY TREE DATA STRUCTURE: file contains basic binary tree

class treeNode {
   private double data;             // data
   private treeNode left, right;		// child nodes

   public treeNode(double d) {this(d, null, null);}
   public treeNode(double d, treeNode l, treeNode r)
      {left = l; right = r; data = d;}

   public double getData() {return data;}				// GET DATA
   public treeNode getLeft() {return left;}			// GET LEFT CHILD (TREE)
   public treeNode getRight() {return right;}		// GET RIGHT CHILD (TREE)
   public void setData(double d) {data = d;}			// SET DATA AT NODE
   public void setLeft(treeNode l) {left = l;}		// SET LEFT CHILD
   public void setRight(treeNode r) {right = r;}	// SET RIGHT CHILD
}



class BinaryTree {
   private treeNode root;						// ROOT NODE OF TREE
   private int items = 0;						// TOTAL ITEMS ON TREE
   private String output, entered = "";	// OUTPUT OF TREE TO PRINT AS STRING

	// CONSTRUCTORS
   public BinaryTree() {root = null;}							// DEFAULT
   public BinaryTree(double d) {root = new treeNode(d);}	// ATTATCH ROOT AS YOU CONSTRUCT

	// EMPTY TREE BOOLEAN METHOD FOR IMPLEMENTOR'S QUERIES
   public boolean isEmpty() {return (boolean)(root == null);}
	
	// LENGTH/SIZE QUERY METHOD
   public int length() {return items;}
	
	// SET ROOT METHOD, NOT FOR USER
   private void setRoot(treeNode r) {root = r;}
	
	// COPY CONSTRUCTOR
   public BinaryTree neatCopy() {
      BinaryTree copied = new BinaryTree();
      if (root != null) {
         String stuff = preorderTraverse();	// CALL TRAVERSAL OF CURRENT TREE
         int bar; String seg;
         while (stuff.indexOf('|') >= 0) {
            bar = stuff.indexOf('|');			// GET LOCATION OF "|" SEPARATOR
            seg = stuff.substring(0,bar);		// READ UP UNTIL "|" SEPARATOR
            copied.insertItem(Double.parseDouble(seg));		// INSERT INTO NEW TREE
            stuff = stuff.substring(bar+1,stuff.length());	// RESET START OF STRING
         }
      }
      return copied;
   }
	
	// RETURNS ITEMS OF TREE AS STRING EXPLICITY AS ENTERED
   public String enteredOrder() {return entered;}
	
	// PREORDER TRAVERSAL OF TREE
   public String preorderTraverse() {
      output = "";
      Preorder(root);
      return output;
   }
   private void Preorder(treeNode t) {
      if (t != null) {
         output += t.getData() + "|";
         Preorder(t.getLeft());
         Preorder(t.getRight());
      }
   }
	
	// INORDER TRAVERSAL OF TREE
   public String inorderTraverse() {
      output = "";
      Inorder(root);
      return output;
   }
   private void Inorder(treeNode t) {
      if (t != null) {
         Inorder(t.getLeft());
         output += t.getData() + "|";
         Inorder(t.getRight());
      }
   }
	
	// POSTORDER TRAVERSAL OF TREE
   public String postorderTraverse() {
      output = "";
      Postorder(root);
      return output;
   }
   private void Postorder(treeNode t) {
      if (t != null) {
         Postorder(t.getLeft());
         Postorder(t.getRight());
         output += t.getData()+"|";
      }
   }

   // PRINT TREE AS STRING (ROOT AS LEFTMOST, LEAFS AS RIGHTMOST)
   public String printTree() {
      output = "";
      if (root != null) OutputTree(root, 0);
      return output;
   }
   private void OutputTree(treeNode where, int depth) {
      if (where.getRight() != null) OutputTree(where.getRight(),depth+10);
      for (int i = 0; i < depth; ++i) output += " ";
      output += where.getData() + "\n";
      if (where.getLeft() != null) OutputTree(where.getLeft(),depth+10);
   }

   // INSERT ITEM ONTO TREE
   public void insertItem(double d) {
      items++;						// INCREASE TOTAL NUMBER OF ITEMS
      entered = entered + d + "|";	// ADD TO ENTERED NUMBER TALLY
      treeNode rt = root;				// ROOT POINTER MARKER
      if (root == null) root = new treeNode(d);	// IF ROOT d.n.e., MAKE CURRENT ITEM ROOT
      else while (rt != null) {		// TRAVERSE TREE TO FIND PROPER PLACEMENT OF NODE
         if (d >= rt.getData()) {
            if (rt.getRight() == null) {rt.setRight(new treeNode(d));break;}
            else rt = rt.getRight();
         } else {
            if (rt.getLeft() == null) {rt.setLeft(new treeNode(d));break;}
            else rt = rt.getLeft();
         }
      }
   }
}