Serialize and Deserialize Binary Tree

I am working on the LeetCode problem 297. Serialize and Deserialize Binary Tree:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

I took inspiration from a correct solution I found to a similar problem on Geeks for Geeks: Serialize and Deserialize a Binary Tree :

class Tree 
{
    public void serialize(Node root, ArrayList<Integer> al) 
    {
        //code here
        if(root == null) {
            al.add(-1);
            return;
        }
        al.add(root.data);
        serialize(root.left,al);
        serialize(root.right,al);
    }
    

    public Node deSerialize(ArrayList<Integer> al)
    {
        //code here
        if(al.get(0) == -1) {
            al.remove(0);
            return null;
        }
        Node newNode = new Node(al.get(0));
        al.remove(0);
        newNode.left = deSerialize(al);
        newNode.right = deSerialize(al);
        return newNode;
    }
}

I tried to adjust this approach for for the LeetCode problem. However, my attempt is not producing the desired output:

public class Codec {
    StringBuilder sb = new StringBuilder();
    public String serialize(TreeNode root) {
        if(root==null) {
            sb.append("^");
            return sb.toString();
        }
        sb.append(String.valueOf(root.val));
        serialize(root.left);
        serialize(root.right);
        return sb.toString();
    }
    public TreeNode deserialize(String data) {
        if(data.charAt(0)=='^') {
            data = data.substring(1);
            return null;
        }
        TreeNode newNode = new TreeNode(Character.getNumericValue(data.charAt(0)));
        data = data.substring(1);
        newNode.left = deserialize(data);
        newNode.right = deserialize(data);
        return newNode;
    }
}

Where did I go wrong?

Answer

Some remarks:

• The Geeks-for-Geeks problem has a different interface: there the “serialisation” is interpreted as storing information in an array (vector), while with the LeetCode problem, serialization is about producing a string.

• Your code has a sb member that may be reused with a second call of serialize. Yet the correct functioning of serialize will at least require that sb initially represents an empty string.

• String.valueOf(root.val) gets appended, but there is no delimiter between two consecutive stringified values, so deserialize will not know how many digits belong to one value. In fact, your deserialize seems to assume each number only consists of one digit. This cannot be assumed.

• In deserialize the assignment data = data.substring(1) will only affect the local variable data, not the data variable of the caller. Note how the Geeks-for-Geeks solution has the advantage it gets an array to work with, which it can mutate. Strings are not mutable, so in the LeetCode problem we cannot use this strategy. You can get out of this by using a third function that you will pass a mutable array.

For instance:

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "^";
        }
        return String.valueOf(root.val) + ","
             + serialize(root.left) + ","
             + serialize(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return deserializeArray(new ArrayList<String>(Arrays.asList(data.split(","))));
    }
    
    private TreeNode deserializeArray(ArrayList<String> arr) {
        String value = arr.remove(0);
        if (value.charAt(0) == '^') {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(value));
        node.left = deserializeArray(arr);
        node.right = deserializeArray(arr);
        return node;
    }
}