Returning an inorder string of a Tree

Question

EDIT This has been resolved by using StringBuilder as suggested in this thread. Thank you :D

Hello,

I have a tree and am trying to return a String of the content in order.

I can currently print out the tree with something like this:

    public void inOrder() {
        if (left != null) left.inOrder();
        System.out.print(content + " ");
        if (right != null) right.inOrder();
    }

But what I want to do is return the String (rather than print out each nodes content while recursing) and I can't work out how to do it. I tried many variations of the code below, but it just returns the last element it finds in the recursion.

 public String inOrder(String string) {
        if (left != null) left.inOrder(string);
        string += content;
        if (right != null) right.inOrder(string);

        return string;
    }

Solution 1

Strings are immutable in java. You are not concatenating new String to old one, you are creating new String and make string variable point to it. Result is that you have many unrelated Strings and string variable points to them in various points in time.

You need to pass mutable object to your function such as StringBuilder. This solution have additional advantage that it's much more efficient because you are avoiding unnecessary Object allocations.

Solution 2

If you want to do this with String concatenation, your second example nearly works - the problem is only that you are throwing away the results of the recursive calls.

/**
 * creates an Inorder-string-view of this tree and appends it to the given string.
 * @return the new String.
 */
public String inOrder(String string) {
    if (left != null)
        string = left.inOrder(string);
    string += content;
    if (right != null)
        string = right.inOrder(string);
    return string;
}

But this is (for larger trees) horrible inefficient, since each += in fact creates a new String, copying the characters of string and content - thus each content string is in fact copied the number of later nodes (in inorder sequence) times (+1). A slightly better way would be this:

public String inOrder() {
    String leftS; String rightS;
    if (left != null)
       leftS = left.inOrder();
    else
       leftS = "";
    if (right != null)
       rightS = right.inOrder();
    else
       rightS = "";
    return leftS + content + rightS;
}

or a bit shorter:

public String inOrder {
   return
      (left != null ? left.inOrder() : "") +
      content +
      (right != null ? right.inOrder() : "");
}

Now each content string is only copied the number of nodes above it times (+1), which for a "usual" (not extremely unbalanced) tree is much smaller. (This variant could easily be parallelized, too.)

But in fact, the StringBuilder version is normally the preferred one, since it copies each content string only one time (when appending it to the StringBuilder), and maybe some more times during internal resizes of the StringBuilder (so if you can estimate the final size before the actual conversion, create a StringBuilder big enough).

Solution 3

Strings are immutable in Java and when you add something to a String, a new object is created. Thus, the change is not visible outside the scope of the method.

Try a StringBuilder instead of String:

public StringBuilder inOrder(StringBuilder string) {
        if (left != null) left.inOrder(string);
        string.append(content);
        if (right != null) right.inOrder(string);

        return string;
}

You could read here: http://www.javaworld.com/javaqa/2000-05/03-qa-0526-pass.html to understand the way Java passes arguments to methods and why Strings immutability is an issue in your original code.

Regards, Sorin.