/*
   BinaryTree.java

   A simple binary tree implementation
   MAH 10/14/01

   */


public class BinaryTree {

    // instance variables
    private String name;        // data to store in the node
    private  int        value;       // data to store in the node
    private  BinaryTree left;
    private BinaryTree right;

    // constructor
    BinaryTree () {
        name = "default";
        value  = 0;
        left = null;
        right = null;
    }

    // constructor
    BinaryTree (String n, int v) {
        name = n;
        value = v;
        left = null;
        right = null;
    }

    // constructor
    BinaryTree (String n, int v, BinaryTree l, BinaryTree r) {
        name = n;
        value = v;
        left = l;
        right = r;
    }

  // For
    public void setSubtrees(BinaryTree l, BinaryTree r) {

        this.left = l;
        this.right = r;
    }

   // two different ways to implement the iterative form

    public void printLeftIterative (BinaryTree t) {

                 BinaryTree temp = t;
                while (temp != null) {
                    System.out.println(temp.name);
                    temp = temp.left;
        }
    }


     public void printLeftIterative () {
                     BinaryTree temp = this;
                    while (temp != null) {
                        System.out.println(temp.name);
                        temp = temp.left;
            }
        }



// two ways to do the recursive form

    public void printLeftRecursive (BinaryTree t) {

       if (t != null) {
            System.out.println(t.name);
            printLeftRecursive(t.left);
        }
    }

   public void printLeftRecursive () {

         System.out.println(this.name);
          if (this.left != null) {
              BinaryTree temp = this.left;
              temp.printLeftRecursive();
          }
    }

  // preorder (tree v)    visit each node before its children
  // visit (v);
  // for each child w of v,
  //     preorder (w)

  // note: we don't need to check for this being null --
  // the method can't have been called on a null object

  public void printPreOrder () {

          System.out.println(this.name);

          if (this.left != null)
               this.left.printPreOrder();

          if (this.right != null)
            this.right.printPreOrder();

  }

// inorder(tree v)   visit the left subtree, visit v, visit the right subtree

  public void printInOrder () {

        if (this.left != null)
             this.left.printInOrder();

         System.out.println(this.name);

         if (this.right != null)
             this.right.printInOrder();
  }

  public void printPostOrder () {

          if (this.left != null)
              this.left.printPostOrder();

          if (this.right != null)
              this.right.printPostOrder();

           System.out.println(this.name);

  }



 // for a tree, Depth First Traversal is equivalent to preorder traversal

  public void printDFS() {
        printPreOrder();
  }

  //  Depth First Search: Here we are looking for a particular object
  // When we find the node that matches the name, we will return the
  // value stored at that node.  If the node is not found we'll return -1

  public int searchDFS(String name) {

      int val = -1;
      if (this.name.equals(name))
          return this.value;           // this ends the method

      if (this.left != null)
          val = this.left.searchDFS(name);

      if (val > -1) return val;     // if found, skip the right side

       if (this.right != null)
           val = this.right.searchDFS(name);

        return val;
  }

  /* Breadth First Traversal is different than the others --
      it requires us to keep track of information about which
      nodes have been visited so far.  We can use our Queue!
      Two methods work together here.
      Note: this is not recursive
      */

  private void printBFSHelper(Queue queue) {

     BinaryTree t;
     // this is for debugging only
     //  System.out.println("Contents of the queue");
     //  queue.printQueue();

      while ((t = (BinaryTree) queue.deQueue()) != null) {

          System.out.println(t.name);
          if (t.left != null)
               queue.enQueue(t.left);

          if (t.right != null)
              queue.enQueue(t.right);

      }
  }

 // The main work is done by printBFSHelper
  public void printBFS() {

      Queue queue = new Queue();
      queue.enQueue(this);
      printBFSHelper(queue);
  }


    public static void main (String args[]) {

        BinaryTree root = new BinaryTree("root", 0);
        BinaryTree a      = new BinaryTree("a", 1);
        BinaryTree b        = new BinaryTree("b", 1);
        root.setSubtrees(a, b);
        a.setSubtrees(new BinaryTree("aa",2), new BinaryTree("ab",2));
        a.left.setSubtrees(new BinaryTree("aaa",3), new BinaryTree("aab",3));

        System.out.println("Printing left subtrees recursively");
        root.printLeftRecursive(root);
        System.out.println("Printing left subtrees recursively another way");
         root.printLeftRecursive();


        System.out.println("Printing InOrder");
        root.printInOrder();
        System.out.println("Printing PreOrder");
        root.printPreOrder();
        System.out.println("Printing PostOrder");
        root.printPostOrder();
        System.out.println("Printing BFS");
        root.printBFS();

        System.out.println("Searching for " + "aa " + root.searchDFS("aa"));
        System.out.println("Searching for " + "bb " + root.searchDFS("bb"));
    }

}