//BinaryTree.java

import java.util.PriorityQueue;

/**
 * A simple, immutable binary tree.
 *
 * @author Zach Tomaszewski
 * @version Oct 19, 2006
 */
public class BinaryTree {

  private TreeNode<Integer> root;

  /**
   * Creates a new binary tree, where the leaf nodes are comprised of members
   * of the given set.  Each inner node contains the sum of its two children
   * nodes.  Therefore, the root contains the sum of all the leaves.
   *
   * @param set  The numbers that will be stored in the leaf nodes
   *             of the new tree
   */
  public BinaryTree(int[] set) {

    //load leaves queue with leaf nodes containing input set
    PriorityQueue<TreeNode<Integer>> leaves =
        new PriorityQueue<TreeNode<Integer>>();

    for (Integer num: set) {
      leaves.add(new TreeNode<Integer>(num));
    }

    //now build tree by combining two the smallest nodes as
    //subtrees of a new inner node
    while (leaves.size() > 1) {
      TreeNode<Integer> left = leaves.poll();
      TreeNode<Integer> right = leaves.poll();
      TreeNode<Integer> root = new TreeNode<Integer>(left.getData() +
                                                     right.getData());
      root.setLeft(left);
      root.setRight(right);
      leaves.add(root);
    }

    if (leaves.size() == 1) { //only one node left, which is the root of tree
      this.root = leaves.poll();
    }else {
      //initial set was empty, so tree will be empty
      this.root = null;
    }
  }


  /**
   * Prints this tree to the screen, as if with {@link #toString()}.
   */
  public void display() {
    System.out.println(this.toString());
  }


  /**
   * Returns a string representation of this binary tree.
   * Leaf nodes are in [brackets];
   * left and right subtrees are grouped in (parentheses).
   */
  public String toString() {
    return toString(root);
  }

  /**
   * Returns a one-line string representation of the given subtree.
   */
  private String toString(TreeNode tree) {
    if (tree == null) {
      return "";
    }else if (tree.isLeaf()) {
      return "[" + tree.getData() + "]";
    }else {
      String result = "(";
      result += toString(tree.getLeft());
      result += " " + tree.getData() + " ";
      result += toString(tree.getRight());
      result += ")";
      return result;
    }
  }


  /**
   * Returns a multi-line String representation of this tree.
   * Subtrees are recursively indented, showing the tree hierarchically.
   */
  public String toStringTree() {
    return toStringTree(root, 0);
  }

  /**
   * Returns a multi-line string representation of the given subtree.
   *
   * @param tree  The tree to print.
   * @param indent  The number of spaces to indent
   *                (increases by 2 for each level).
   */
  private String toStringTree(TreeNode tree, int indent) {
    if (tree == null) {
      return "";
    }
    String indentation = "";
    for (int i = 0; i < indent; i++) {
      indentation += " ";
    }
    if (tree.isLeaf()) {
      return "[" + tree.getData() + "]\n";
    }else {
      String result = "(" + tree.getData() + ")\n";
      result += indentation + "Left: " +
                  toStringTree(tree.getLeft(), indent + 2);
      result += indentation + "Right: " +
                  toStringTree(tree.getRight(), indent + 2);
      return result;
    }
  }

  /**
   * Tests a BinaryTree implementation by creating a tree and printing it.
   *
   * @param args  Not used.
   */
  public static void main(String[] args) {

    //create new BinaryTree with given set
    int[] ints = {5, 3, 4, 2, 1};

    System.out.println("Creating new BinaryTree with " +
                        java.util.Arrays.toString(ints));
    BinaryTree tree = new BinaryTree(ints);

    System.out.print("Displaying tree: ");
    tree.display();

    System.out.println("Displaying tree another way: ");
    System.out.println(tree.toStringTree());

    System.out.println("\nTests DONE.");

  }//end main


}//end class