Recursively Writing to a String in Memory : Java

May 7, 2022

I’m working with trees for the first time. Learning about preOrder, postOrder and inOrder traversal. All of the functions I read online simply print the string to standard output, for example:

    void printPreorder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        
        printPreorder(node.left);
        
        printPreorder(node.right);
    }

What if I want to write to a string in memory and then return the result?

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    public static String visit(Node node, String buffer) {
        if (node != null) {
            buffer += node.data + " ";
            visit(node.left, buffer);
            visit(node.right, buffer);
        }
        return buffer;
    }
    
    public static void main(String args[]) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(5);
        Node n4 = new Node(3);
        Node n5 = new Node(4);
        Node n6 = new Node(6);

        n1.right = n2;
        n2.right = n3;
        n3.left = n4;
        n3.right = n6;
        n4.left = n5;

        System.out.println(visit(n1, ""));
    }

When I debug my preOrder, I notice it reverts the string to a former state in the call stack, despite my call stack returning the latest string.

Why is the string being overwritten in memory, or how can I fix my function to return the desired output?

Visual Tree:

>Solution :

The problem is that you don’t modify buffer, you re-assign it to a new value, so what happen in the recursive call is lost

buffer = buffer + node.data + " ";

Use a mutable object instead like a StringBuilder

public static StringBuilder visit(Node node, StringBuilder buffer) {
    if (node != null) {
        buffer.append(node.data).append(" ");
        visit(node.left, buffer);
        visit(node.right, buffer);
    }
    return buffer;
}

// System.out.println(visit(n1, new StringBuilder()));

Or don’t use one object that collect the values, but return them

public static String visit(Node node) {
    if (node != null) {
        return node.data + " " + visit(node.left) + visit(node.right);
    }
    return "";
}

// System.out.println(visit(n1));