Building binary tree from preorder bitstring

Question

I am trying to do an assignment but I'm having trouble with the first step. The link below is the assignment for context:

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B1DkmkmuB-leNDVmMDU0MDgtYmQzNC00OTdkLTgxMDEtZTkxZWQyYjM4OTI1&hl=en

A sample input is:

a0
0
a00
ab000

Which gives an output of:

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 unable to progress on the assignment because I am stuck on actually building the binary tree from the input. The code I have been able to come up with so far is below:

public class btsmall {
    int k = 0;
    char[] cArray;

    public static void main(String[] args) throws IOException {
        new btsmall().run();
    }

    static class Node {
        Node left;
        Node right;
        char value;

        public Node(char value) {
            this.value = value;
        }
    }

    public void run() throws IOException {
        String preorder;
        InputStreamReader input = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(input);

        while ((preorder = reader.readLine()) != null) {
            cArray = preorder.toCharArray();
            Node tree = null;
            insert(tree);
            preorder(tree);
            k = 0;
        }
    }

    public void insert(Node node) {
        if (cArray[k] == (char) 0) {
            node = new Node((char) 0);
            node.left = node.right = null;
            k++;
        } else {
            node = new Node(cArray[k]);
            k++;
            insert(node.left);
            insert(node.right);
        }
    }

    public void preorder(Node node) {
        if (node != null) {
            System.out.println(node.value + " ");
            preorder(node.left);
            preorder(node.right);
        }
    }
}

I am trying to test that I'm building the binary tree correctly with the preorder method, but whenever I run the program it seems to be stuck in an infinite loop somewhere. Can anyone help point out what is causing it? And am I actually on the right track with this? Does anyone have any hints on how I should go about building this particular binary tree?

Thanks.

Answer 1

it's not in an infinite loop. its just waiting for input from System.in

Answer 2

(char) 0 is the character which is represented by Unicode U+0000 (NUL). You want to use '0' (U+0030) in your test.

As an aside, the problem setter has not stated whether the given preorder is depth-first or breadth-first (or something else), so one cannot be certain how to rebuild the tree correctly.