2

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 :)

Sanket Makani
  • 2,491
  • 2
  • 15
  • 23
Guy
  • 43
  • 5
  • your algorithm saves only last node because you don;t save results from treeToPost(node.left, post) and treeToPost(node.right, post) – dehasi May 11 '17 at 10:21
  • You could use a inorder-traversal and insert the values of each node as they appear inorder in the tree and insert an opening bracket each time you step down one level (towards the leaves) and a closing-bracket each time you step up one level. And thats pretty much how you create an infix-representation of your tree. Of course this would introduce brackets with a single term inside them, but thats not too hard to fix, if necessary. –  May 11 '17 at 10:24

1 Answers1

2

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.

Thijs Steel
  • 1,190
  • 7
  • 16
  • Thank you a lot for your answer! Feeling a bit dumb for not thinking about it myself, it only had a little problem of printing too many parenthesis, which was easy to fix. – Guy May 11 '17 at 10:46
  • there is no such thing as too many parenthesis. Only parenthesis that are unnecessary ;). – Thijs Steel May 11 '17 at 11:09