Serialize and Deserialize Binary Tree

Problem

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.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 104].

• -1000 <= Node.val <= 1000

Solution

We use level-order traversal for both operations.

Serialization: Start with the root in a queue. Remove one item at a time and add its value to the string. For a real node, add its left and right children to the queue, even if they are null. Write null for each missing child. These markers preserve the tree’s shape: without them, we would know the node values but not where every child belongs.

Deserialization: Read the first value as the root and put it in a queue. Remove the next parent from the queue, then read the next two values as its left and right children. Create and queue each child whose value is not null. Repeat until all values have been read.

Revision cue: Serialize: parent → left → right, including null. Deserialize: take a parent → read its next two children.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){

            TreeNode node = queue.poll();

            if(node == null){
                sb.append("null ");
                continue;
            }

            sb.append(node.val);
            sb.append(" ");
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        
        if(data == null || data == "") return null;

        String[] values = data.split(" ");

        if(values[0].equalsIgnoreCase("null")) return null;

        Queue<TreeNode> queue = new ArrayDeque<>();
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        queue.offer(root);

        for(int i=1; i<values.length; i++){
            
            TreeNode node = queue.poll();

            if(!values[i].equalsIgnoreCase("null")){
                node.left = new TreeNode(Integer.parseInt(values[i]));
                queue.offer(node.left);
            }

            i+=1;

            if(!values[i].equalsIgnoreCase("null")){
                node.right = new TreeNode(Integer.parseInt(values[i]));
                queue.offer(node.right);
            }
        }

        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));