Java: Serialize and Deserialize Binary Tree

Thought Process

To serialize and deserialize a binary tree, we can use a level-order traversal (BFS). For serialization, we traverse the tree level by level and store each node's value in a string, using "null" to represent missing nodes. For deserialization, we reconstruct the tree by processing the serialized string and building the tree level by level. This approach ensures that the tree structure is preserved and reconstructed accurately. 

/**
 * 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) {

        // 1,2,3,null,null,4,5
        if(root == null)
            return "null"; 

        Queue<TreeNode> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        q.offer(root);

        while(!q.isEmpty()){

            TreeNode nod = q.poll();

            if(nod==null){
                sb.append("null,"); // 1,2,3,null,null,4,5,null,null,null,null
            }
            else{
                sb.append(nod.val).append(','); 
                q.offer(nod.left);
                q.offer(nod.right);
            }
        }
        int n = sb.length();
        sb.deleteCharAt(n-1); // To remove last comma
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        if(data=="null")
            return null;

        String[] list = data.split(","); 
        TreeNode root = new TreeNode(Integer.parseInt(list[0]));

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

        int idx = 1;
         // 1,2,3,null,null,4,5,null,null,null,null 
        while(!q.isEmpty() && idx<list.length){

            TreeNode nod = q.poll(); // Structure of Queue after first polling: 2,3,4,5

            if(!list[idx].equals("null")){
                nod.left = new TreeNode(Integer.parseInt(list[idx])); // Convert String to Integer
                q.offer(nod.left);
            }
            idx++;

            if(!list[idx].equals("null")){
                nod.right = new TreeNode(Integer.parseInt(list[idx])); // Convert String to Integer
                q.offer(nod.right);
            }
            idx++;

        }
        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));

Code Complexity

Time Complexity: O(n)

Both serialization and deserialization visit each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(n)

The space used by the queue during serialization and deserialization depends on the maximum number of nodes at any level. In the worst case, the space complexity is O(n).

Code copied!