Serialize and Deserialize Binary tree

XXX. Serialize and Deserialize Binary Tree

Tree

Recursion

Serialization

Problem Statement:

Design an algorithm to serialize and deserialize a binary tree. Serialization is the process of converting a tree into a single string, and deserialization is the reverse operation.

Your serialized and deserialized tree should preserve the structure of the binary tree.

Algorithm:

This solution uses a recursive approach for both serialization and deserialization:

1. For serialize:
   • If the current node is null, append X to the serialized string to represent a null node.
   • Otherwise, append the node's value, followed by recursively serializing its left and right children.
2. For deserialize:
   • Split the serialized string into an array of node values.
   • Use a queue to process each value and recursively reconstruct the tree by creating nodes for non-null values and connecting them.

Complexity:

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once during serialization and deserialization.
Space Complexity: O(n), for the recursion stack and the serialized data storage.

Java Implementation:

public class Codec {

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

    private void serialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("X").append(","); // Represent null nodes as 'X'
        } else {
            sb.append(node.val).append(","); // Append node value
            serialize(node.left, sb); // Serialize left subtree
            serialize(node.right, sb); // Serialize right subtree
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodeList = data.split(","); // Split the serialized string
        return deserialize(nodeList, new int[1]);
    }

    private TreeNode deserialize(String[] nodeList, int[] index) {
        String s = nodeList[index[0]++];
        if (s.equals("X")) return null; // Null node encountered
        
        TreeNode node = new TreeNode(Integer.valueOf(s)); // Create node with value
        node.left = deserialize(nodeList, index); // Reconstruct left subtree
        node.right = deserialize(nodeList, index); // Reconstruct right subtree
        return node;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}