Creating a balanced binary tree with a string of letters
<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>