public void inOrderTraversal(TreeNode node) {
    if(node == null) {
        return; 
    }
    inOrderTraversal(node.getLeft());
    System.out.print(node.getKey() + " ");
    inOrderTraversal(node.getRight());

}

I wrote this code for going through a binary search tree and printing out the items in order from low to high. it works just fine but i need to get it to return a String instead of just printing them out so that it will work with an applet im using. however when i change the return type to String it wont work unless i add another return outside of the if()???

public String inOrderTraversal(TreeNode node) {
    String w = "";
    if(node == null) {
        return w; 
    }
    inOrderTraversal(node.getLeft());
    w += node.getKey() + " ";
    inOrderTraversal(node.getRight());

}

something closer to this is what i need but it wont work this way? anyone who could help explain to me how to make this work. Any suggestions would be greatly appreciated!

You could do 2 ways, either pass in a string for concatenation and return it at the end, or return a built string plus its own at the end. If you are using a local variable, use it to concatenate with the return value from recursion call. To me, the easiest way is to pass in a String so no need to declare a local variable.

public String inOrderTraversal(TreeNode node, String result) {
  ...
}

// when call
System.out.println(inOrderTraversal(node, ""));

Edited 4 Years Ago by Taywin

Passing in a String for concatenation (if I understand our suggestion properly) won't work because String is immutable - you will have to create a new String but have no way to update the reference that was passed in. It would work ok with a StringBuilder.
Returning a new String is OK, as is the instance variable ("local" in Java terminology refers to variables declared inside methods, which is not what you intended, http://docs.oracle.com/javase/tutorial/java/nutsandbolts/variables.html )

When you say your function will return a string, you need to return a string in every execution path. You need to return the result of the concatenation to the calling function. Also, take the return values from the recursive calls and concatentate them to this call's return value. I like putting commas between my elements, just to be clearer.

public String inOrderTraversal(TreeNode node)
{
    String w = "";

    if(node == null)
    {
        return w;
    }
    w += inOrderTraversal(node.getLeft());
    w += node.getKey() + ", ";
    w += inOrderTraversal(node.getRight());
    return w;
}

If I knew how StringBuilder works in Java, I would probably use that instead of always concatenating a string, as it is likely more efficient doing a series of appending operations.

Edited 4 Years Ago by Nutster: grammar fix. Formatting adjustment.

This article has been dead for over six months. Start a new discussion instead.