title: Creating a balanced binary tree with a string of letters
body: <p>I'm trying to create a balanced tree with a string of letters. If you put "ABCDE" for string, your code is expected to give an output something like this.</p>
  
  <p>INPUT : "ABCDE"</p>
  
  <p>OUTPUT :</p>
  
  <pre><code> .......................................................
                              +                                                              
              +                              E                              
      +              +              --              --              
  A      B      C      D      --      --      --      --      
  .......................................................
  </code></pre>
  
  <p>The book suggests me to first create an array of one-node tree whose root will be each character of the string. Then, make a three-node tree out of each pair of one-node trees, making a new + node for the root which will result in a forest of three - node trees. </p>
  
  <p>I know this problem is a stepping-stone to ultimately write the Huffman tree.</p>
  
  <p>I'm having trouble putting the three-node tree back into the array with one-node trees and then make a 7-node tree by combining the two three-node trees and so on.</p>
  
  <p>Below is my code, </p>
  
  <pre><code>import java.util.*; // for Stack class
  
  class StringNode {
    public char iData; // data item (key)
    public StringNode leftChild; // this node's left child
    public StringNode rightChild; // this node's right child
  
    StringNode(char d) {
      iData = d;
    }
  
    public void displayNode() // display ourself
    {
      System.out.print('{');
      System.out.print(iData);
      System.out.print("} ");
    }
  } // end class Node
  
  class STree {
    private StringNode root; // first node of tree
    public String sequence;
  
    // -------------------------------------------------------------
    public STree() // constructor
    {
      root = null;
    } // no nodes in tree yet
  
    public void makeBalanceTree() // creating a balanced tree
    {
      StringNode array[] = new StringNode[sequence.length()];
  
      for (int i = 0; i &lt; sequence.length(); i++)
        array[i] =
            new StringNode(sequence.charAt(i)); //fill array with node holding each character as key
  
      STree forest[] = new STree[array.length]; //make a forest of trees
      for (int j = 0; j &lt; array.length; j++) { //store each node as the root of the tree
        forest[j] = new STree();
        forest[j].root = array[j];
      }
  
      int count = sequence.length();
      while (count == 0) {}
    }
  
    public void displayTree() {
      Stack globalStack = new Stack();
      globalStack.push(root);
      int nBlanks = 32;
      boolean isRowEmpty = false;
      System.out.println("......................................................");
      while (isRowEmpty == false) {
        Stack localStack = new Stack();
        isRowEmpty = true;
  
        for (int j = 0; j &lt; nBlanks; j++) System.out.print(' ');
  
        while (globalStack.isEmpty() == false) {
          StringNode temp = (StringNode) globalStack.pop();
          if (temp != null) {
            System.out.print(temp.iData);
            localStack.push(temp.leftChild);
            localStack.push(temp.rightChild);
  
            if (temp.leftChild != null || temp.rightChild != null) isRowEmpty = false;
          } else {
            System.out.print("--");
            localStack.push(null);
            localStack.push(null);
          }
          for (int j = 0; j &lt; nBlanks * 2 - 2; j++) System.out.print(' ');
        } // end while globalStack not empty
        System.out.println();
        nBlanks /= 2;
        while (localStack.isEmpty() == false) globalStack.push(localStack.pop());
      } // end while isRowEmpty is false
      System.out.println("......................................................");
    } // end displayTree()
  } // end class Tree
  
  public class StringTreeApp {
    public static void main(String[] args) {
      int value;
      STree theTree = new STree();
      theTree.sequence = "ABCDE";
      theTree.makeBalanceTree();
      theTree.displayTree();
    } // end main()
  } // end class TreeApp
  </code></pre>