Building a BinaryTree from an InOrder String Representation

Question

I am given a String like: (((!D!)B!)A((!F(!H!))C(!G!))) where there is never any whitespace. A '!' means that there is no child to that side of the node. To visualize this, the String mentioned previously would look like: https://i.sstatic.net/WywYm.png

I must have a constructor that can call a recursive method to build the tree by passing in the String, which is what I have here:

public BinaryTree(String tree) {
    //build the tree from the inOrder representation of the tree
    //in the inOrder representation an empty tree is ! and a non-empty tree is (leftdataright)
    if(tree.charAt(0) == '!') root = null;
    root = buildTree(tree).root;
}

From here I enter into by private BuildTree method, which is supposed to use recursion and return a reference to the root of the fully assembled tree. The code I have for this is:

private BinaryTree buildTree(String tree) {
    char data = tree.charAt(0);
    BinaryTree b1;
    BinaryTree b2;      
    if(tree.charAt(0) == '!') return new BinaryTree();
    b1 = buildTree(tree.substring(1, tree.length()));
    b2 = buildTree(tree.substring(1, tree.length()));
    return new BinaryTree(b1, data, b2);
}

I guess what I'm confused on is the InOrder representation, where you don't run into the root of the full tree until you are very far into the String. My current code doesn't do much of anything, and I'm just completely lost on how this can be accomplished without knowing the root right away. If there is any way someone can explain this better to get me closer to a solution, please let me know. Thank you.

Answer 1

How about something like this:

private static BinaryTree buildTree(String tree) {
    try {
        return buildTree(new StringReader(tree));
    } catch (IOException ex) {
        throw new RuntimeException(ex.getMessage());
    }
}

private static BinaryTree buildTree(Reader in) throws IOException {
    char c = (char)in.read();
    if (c == '!') {
        return null;
    } else if (c != '(') {
        throw new IOException("Syntax error");
    }
    BinaryTree left = buildTree(in);
    char data = (char)in.read();
    BinaryTree right = buildTree(in);
    c = (char)in.read();
    if (c != ')') {
        throw new IOException("Syntax error");
    }
    return new BinaryTree(left, data, right);
}