Unable to create a binary tree properly?

I am trying to build a binary tree from a string input piped to System.in with Java. Whenever a letter from a-z is encountered in the string I am making an internal node (with 2 children). Whenever a 0 is encountered in the string I am making an external node (a leaf). The string is in preorder, so just as an example, if I had an input such as:

abcd000e000

I am supposed to make the following binary tree

            a
           / \
          b   0
         / \
        c   e
       / \ / \
      d  00   0
     / \
    0   0

At least that is what I think I am supposed to make according to the assignment details (in a link below). We were also given sample input and output for the entire program:

Input

a0

0

a00

ab000

Output

Tree 1:

Invalid!

Tree 2:

height: -1

path length: 0

complete: yes

postorder:

Tree 3:

height: 0

path length: 0

complete: yes

postorder: a

Tree 4:

height: 1

path length: 1

complete: yes

postorder: ba

I am trying to implement a program that will do this for me with Java, but I don't think I am making the binary tree correctly. I have provided the code I have come up with so far and detailed in the comments above each method what trouble I have run into so far while debugging. If more context is needed the following link details the entire assignment and what the ultimate goal is supposed to be (bu开发者_JAVA技巧ilding the binary tree is only the first step, but I'm stuck on it):

Link to Assignment

import java.io.*;

// Node
class TreeNode {
    char value;
    TreeNode left;
    TreeNode right;
}

// Main class
public class btsmall {
    // Global variables
    char[] preorder = new char[1000];
    int i = 0;

    // Main method runs gatherOutput
    public static void main(String[] args) throws IOException {
        new btsmall().gatherOutput();
    }

    // This takes tree as input from the gatherOutput method
    // and whenever a 0 is encountered in the preorder character array
    // (from a string from System.in) a new external node is created with
    // a value of 0. Whenever a letter is encountered in the character
    // array, a new internal node is created with that letter as the value.
    //
    // When I debug through this method, the tree "appears" to be made
    // as expected as the tree.value is the correct value, though I 
    // can't check the tree.left or tree.right values while debugging
    // as the tree variable seems to get replaced each time the condition
    // checks restart.
    public void createTree(TreeNode tree) throws IOException {
        // Check that index is not out of bounds first
        if (i >= preorder.length) {
            i++;
        } else if (preorder[i] == '0') {
            tree = new TreeNode();
            tree.value = '0';
            tree.left = tree.right = null;
            i++;                
        } else {
            tree = new TreeNode();
            tree.value = preorder[i];
            i++;
            createTree(tree.left);
            createTree(tree.right);
        }
    }

    // Supposed to print out contents of the created binary trees.
    // Intended only to test that the binary tree from createTree()
    // method is actually being created properly.
    public void preorderTraversal(TreeNode tree) {
        if (tree != null) {
            System.out.println(tree.value + " ");
            preorderTraversal(tree.left);
            preorderTraversal(tree.right);
        }
    }

    // Reads System.in for the Strings used in making the binary tree
    // and is supposed to make a different binary tree for every line of input
    //
    // While debugging after the createTree method runs, the resulting tree variable
    // has values of tree.left = null, tree.right = null, and tree.value has no value
    // (it's just a blank space).
    //
    // This results in preorderTraversal printing out a single square (or maybe the square
    // is some character that my computer can't display) to System.out instead of all 
    // the tree values like it's supposed to...
    public void gatherOutput() throws IOException {
        InputStreamReader input = new InputStreamReader(System.in); 
        BufferedReader reader = new BufferedReader(input);

        String line = null;
        TreeNode tree = new TreeNode();
        while ((line = reader.readLine()) != null) {
            preorder = line.toCharArray();
            createTree(tree);
            preorderTraversal(tree);
            i = 0;
        }
    }
}

Can anyone help me with building the binary tree properly and point out what I am doing wrong that would result in the output I'm currently getting? Am I at least on the right track? Any hints?

Thanks.

EDIT:

Here's a picture of the "square" output (this is in Eclipse).

---

Your createTree() method ... doesn't create a tree.

You never attach internal nodes to anything ... you just create them, insert the value, then pass them to the next createTree() call (which does the same).

---

A quick fix can be a simple modification of your createTree(..) method,

public void createTree(TreeNode tree) throws IOException {
    // Check that index is not out of bounds first
    if (i >= preorder.length) {
        i++;
    } else if (preorder[i] == '0') {
        tree.value = '0';
        tree.left = tree.right = null;
        i++;                
    } else {
        tree.value = preorder[i];   
        i++;
        tree.left = new TreeNode();
        createTree(tree.left);
        tree.right = new TreeNode();
        createTree(tree.right);
    }
}

Notice you were creating a TreeNode inside this method, whereas it was already passed as an argument. So, you were not at all using the same. Whatever you did was not in the original TreeNode passed.

NB: Not arguing about the correctness of binary tree. Just fix a problem in hand. This might help the OP.

---

but I don't think I am making the binary tree correctly

Yes, it is incorrect. In binary tree one sub-tree is "less" than current element, another one is "more". You have, for example, "b" as the parent for "c" and "e", while (if followed natural sorting) both "c" and "e" are "more".

You need to rebalance you tree in the process.

P.S. I don't know what zeros supposed to mean in the input, but if the input is limited the simplest way to build a binary tree from a sorted sequence is:

1. load whole sequence into an array
2. get middle element as the root one
3. repeat step 2 recursively for the sub-arrays on the left and right of the root element

Update

And yes, as stated in some other answer, you need to have something like:

    } else if (preorder[i] == '0') {
        TreeNode subTree = new TreeNode();
        subTree.value = '0';
        tree.rigth = subTree;
        i++;  

and then pass subTree into recursive call.

---

Also I see an implementation problem:

    while ((line = reader.readLine()) != null) {

does not seem to be a correct stop condition. It will loop forever because if you press just enter, line will not be null, but an empty string.

This one is more suitable:

    while (!(line = reader.readLine()).equals("")) {