// Collection of BST methods for CS 112


public class BinaryTree {

	public static class Node {
		int key;
		Node left;
		Node right;

		public Node(int k) {
			left = null;
			right = null;
			key = k;
		}

		public Node(int k, Node left, Node right) {
			key = k;
			this.left = left;
			this.right = right;

		}
	}

	// Sum up all the numbers in the tree

   public static int sum(Node t) {
		if (t == null)
			return 0;
		else
			return p.item + size(t.left) + size(t.right);
	}


   public static boolean member(Node t, int key) {
		if (t == null)
			return false;
		else if (key < t.key) {
			return member(t.left, key);
		} else if (key > t.key) {
			return member(t.right, key);
		} else
			return true;
	}


	// Find a node with a given key and return a pointer to it or null if not found
   //    This can be used to implement get(...) from the textbook

   public static Node lookup(Node t, int key) {
		if (t == null)
			return null;
		else if (key < t.key) {
			return lookup(t.left, key);
		} else if (key > t.key) {
			return lookup(t.right, key);
		} else
			return t;
	}



   // Recursively insert into tree, same as put(....) from the textbook

	public static Node insert(Node t, int key) {
		if (t == null)
			return new Node(key);
		else if (key < t.key) {
			t.left = insert(t.left, key);
			return t;
		} else if (key > t.key) {
			t.right = insert(t.right, key);
			return t;
		} else
			return t;
	}

   // Recursively reconstructs tree without the key n in it

 public static Node delete(int n, Node t) {
   if (t == null)                             // Case 1: tree is null
     return t;
   else if (n < t.key) {                      // Case 2: key n is in left subtree
     t.left = delete(n, t.left);
     return t;
   } else if (n > t.key) {                    // Case 3: key n is in right subtree
     t.right = delete(n, t.right);
     return t;
   } else                                     // Case 4: found key n at root; 
           if (t.left == null)                // Case 4a: no left child, so reroute around this node
     return t.right;
   else if (t.right == null)                  // Case 4b: no right child, ditto
     return t.left;
   else {                                     // Case 4c: both children exist, so move minimal key in right subtree up 
     Node min = findMin(t.right);             //    Preserve a pointer to this minimal node and then
     t.right = deleteMin(t.right);            //    reconstruct the right subtree without it
     min.left = t.left;                       //    Finally, replace root node with min node
     min.right = t.right;
     return min;
   }
 }
 
 // return a pointer to the minimal element in r
 
 public static Node findMin(Node r) {
   if(r.left == null)          // this is the minimal node
     return r;
   else
     return findMin(r.left);
 }
 
 // reconstruct the tree r without its minimal element
 
 public static Node deleteMin(Node r) {
   if(r.left == null)
     return r.right;
   else {
     r.left = deleteMin(r.left);
     return r; 
   } 
 }

   // Recursively traverse the tree, printing out the keys, one per line; by changing order
   //    of statements, can get all 6 traversals:
   //    
   //    Preorder          V L R
   //    Inorder           L V R
   //    Postorder         L R V
   //    Reverse Preorder  V R L
   //    ReverseInorder    R V L
   //    ReversePostorder  R L V

   public static void traverse(Node t) {
       if(t != null) {
           traverse(t.left);             // L
           visit(t);                     // V
           traverse(t.right);            // R
       }
   } 

   public static void visit(Node t) {
      System.out.println(t.key);
   }

   // Recursively print out a diagram of the tree sideways

	public static void printIndentedTree(Node t) {
		System.out.println();
		printIndentedTreeAux(t, "");
		System.out.println();
	}

	   public static void printIndentedTreeAux(Node t, String indent) {
		   if (t != null) {
		    	printIndentedTreeAux(t.right, indent + "   "); // add three spaces to indent
			    System.out.println(indent + t.key);
			    printIndentedTreeAux(t.left, indent + "   "); // add three spaces to indent
		   }
	   }

}