// Name   :
// Matric#:
// Group# :
// CS1102 Lab 8B
//
// A copy of this program can also be found at:
// http://www.comp.nus.edu.sg/~cs1102/B/b.html
//
// TITLE: Building a balance binary search tree (BST) "in batch".
//
// In this lab, you are to write a method that builds a balanced BST 
// containing a given sequence of elements.  
//
// Normally, we build a BST by creating an empty tree, then inserting 
// elements into the tree one-by-one.  However, if we insert the elements 
// in sorted order, we will end up with a "linear" trees.  We need to 
// perform rotation to maintain the balance of the tree.  Fortunately, 
// if we know the sequence of elements to insert in advance, we do not 
// need to perform any rotation.  We can sort the input elements, and 
// build the tree "in batch" and achieve a tree that is almost perfectly 
// balance -- for any node, the number of nodes in the left-subtree and 
// the number of nodes in the right sub-tree differs by at most 1.  
// (Note that this is even stronger balance condition than AVL tree!)
//
// You are given the elements to be inserted into a BST, stored in a 
// _sorted_ array.  Your goal is to implement the constructor of a 
// BSTree so that it initializes the tree to a balanced BST using 
// the elements in this array. You should build the tree by assignment 
// of references only.  No insertion or rotation are allowed.
// 
// Complete the constructor for class BSTree.  You may find it necessary
// to write an auxiliary recursive method.
//
// Important Remarks:
// - make sure you think, plan, and verify your solution before you begin 
//   coding.
// - think recursively!


/**  
 * A Node in a BST.  Each node has a integer element, and two references to 
 * the left and right node.   Note that left, right and element are not 
 * private.  Therefore, you can access their values directly just like in 
 * the notes and textbook (e.g., t.left).
 **/
class BinaryNode {
  int element; //element of the node, represents the node.
  BinaryNode left;
  BinaryNode right;
  
  public BinaryNode(int k) 
  {
    element = k;
    left = right = null;
  }
}


/**
 * A Binary Search Tree.  It has a root reference.
 **/
class BSTree {

  BinaryNode root; //root of the tree

  /**
   * Constructor for BSTree.  Initialize this BSTree so that it has 
   * N BinaryNodes, each containing a different value from array a[].  
   * The constructed tree must be balanced.  You should set root to 
   * the root of the constructed tree.  You may find it necessary to
   * write an auxillary recursive method to build the tree.
   * @param a is an array of N sorted integers.
   */
  public BSTree(int[] a) { 
     // WRITE YOUR CODE HERE.
  }

  /**
   * prints out the tree for debugging.  Just a wrapper around
   * auxiliary method print(int level, BinaryNode t).
   */
  public void print() {
     print(0, root);
     System.out.println();
  }


  /**
   * Auxiliary method for printing out the tree.
   */ 
  private void print(int depth, BinaryNode t)
  {
     if (t == null)
         return;
     System.out.println(t.element);
     
     if (t.left != null)
     {
         for (int i = 0; i <= depth; i++)
             System.out.print(" ");
         print(depth + 1, t.left);
     }
  
     if (t.right != null)
     {
         for (int i = 0; i <= depth; i++)
             System.out.print(" ");
         print(depth + 1, t.right);
     }
  }
}

public class Lab8B {
  public static void main(String[] args) {
    int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8}; //the given sorted array.

    BSTree t = new BSTree(a); //call the BSTree constructor.
    t.print();                //print the tree.

    int[] b = {8}; //the given sorted array.

    t = new BSTree(b); //call the BSTree constructor.
    t.print();                //print the tree.

    int[] c = {0, 1, 2, 3, 4, 5}; //the given sorted array.

    t = new BSTree(c); //call the BSTree constructor.
    t.print();                //print the tree.
  }
}