CODEWITHSUNDEEP
javadatabasealgorithmtree
Guy
Guy

Reputation: 43

Making a string of postorder data of a given tree

As part of my assignment , I am given an expression tree and I need to convert it to a in-fix with O(n) run-time. For example,

given tree

To convert this tree to "( ( 1 V ( 2 H ( 3 V 4 ) ) ) H ( 5 V 6 ) )". I couldn't think of a way to convert it straight to infix so I thought of first converting it to post-fix and than to in-fix. (If there's a better way please tell me).

Now, my problem is with converting the tree to post-order. I have tried the following:

    private String treeToPost(Node node, String post) {
    if (node != null) {
        treeToPost(node.left, post);
        treeToPost(node.right, post);
        post = post + node.data.getName();
    }
    return post;
}

Now I have two problems with this method, the first one is that doesn't work because it only saves the last node it traveled, the second one is that I'm not sure it will run at O(n) because it will have to create a new string each time. I found a solution to this issue here but it used StringBuilder which I am not allowed to use. I thought of making an array of chars to save the data , but because I dont know the size of the tree I cant know the size of the needed array. Thank you for your time :)

Upvotes: 2

Views: 548

Answers (1)

Thijs Steel
Thijs Steel

Reputation: 1272

Going directly to infix is probably easier, just always add parenthesis.

Secondly, doing something like this will save all nodes:

private String treeToPost(Node node) {
    String returnString = "";
    if (node != null) {
        returnString += treeToPost(node.left);
        returnString += treeToPost(node.right);
        returnString += node.data.getName();
    }
    return returnString;
}

For infix, this should work

private String treeToPost(Node node) {
    String returnString = "";
    if (node != null) {
        returnString += "(" + treeToPost(node.left);
        returnString += node.data.getName();
        returnString += treeToPost(node.right) + ")";
    }
    return returnString;
}

These both make new String objects each time. So i think it technically is O(n^2), because the string grows each time, but no professor of mine would deduct points for that. However if you want to avoid this behaviour and can't use StringBuilder. You can use a CharArrayWriter. This is a buffer that grows dynamically. You can then make two methods. One that appends to the buffer and returns nothing. And one that returns a String. You would then call the buffer one from inside the String one.

Upvotes: 2

Related Questions