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;
    }

Answer 1

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

Answer 2

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.

Answer 3

Java is pass by value. A reference to an object passed to a method can't be changed by this method. You can change the content of an object, but you can't do that with Strings, because they are immutable (their content can't change).

The line

string += content;

affects a new String object to the string variable. It doesn't change the content of the original String object.

You need to pass a StringBuilder instance to your method, and append to this StringBuilder:

public String inOrder() {
    StringBuilder strinBuilder = new StringBuilder();
    postOrder(stringBuilder);
    return stringBuilder.toString();
}

private void postOrder(StringBuilder stringBuilder) {
    if (left != null) left.postOrder(stringBuilder);
    if (right != null) right.postOrder(stringBuilder);
}

Answer 4

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.

Answer 5

Easy to get using Recursive Solution:

Node Class

public static class Node {

    int key;
    int nodeHeight;
    Node left;
    Node right;

    public Node(int key) {
        this.key = key;
        this.nodeHeight = 1; // Initial Height will always be one
    }

    public Node getMin() {
        //IF current node has missing left, that means this is the last item at left
        if (left == null)
            return this;
        else
            return left.getMin();// Rerun the same function on current node's left
    }
}

Implementation:

public class AVL {

    Node root;

    public AVL() {
    }

    String getInOrderString() {
       return getInOrderString(root);
    }

    private String getInOrderString(Node node) {
      if (node == null) return "";
      return getPreOrderString(node.left) + node.key + " " + getPreOrderString(node.right);
    }
}