Returning an inorder string of a Tree

java recursion tree inorder
guesswork picture guesswork · Feb 22, 2011 · Viewed 11.3k times · Source

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

Slartibartfast picture Slartibartfast · Feb 22, 2011

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.

Related questions

How to deep copy a Binary Tree?

I would like using my own Node class to implement tree structure in Java. But I'm confused how to do a deep copy to copy a tree. My Node class would be like this: public class Node{ private String value; …

Read More
Diameter of Binary Tree - Better Design

I have written a code for finding diameter of Binary Tree. Need suggestions for the following: Can I do this without using static variable at class level? Is the algorithm fine/any suggestions? public class DiameterOfTree { public static int diameter = 0; …

Read More
Java recursive Fibonacci sequence

Please explain this simple code: public int fibonacci(int n) { if(n == 0) return 0; else if(n == 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2); } I'm confused with the last line especially because if n = 5 for example, then fibonacci(4) + fibonacci(3) …

Read More