Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root):
        def helper(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            helper(node.left)
            helper(node.right)
        vals = []
        helper(root)
        return ','.join(vals)

    def deserialize(self, data):
        def helper():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = helper()
            node.right = helper()
            return node
        vals = iter(data.split(','))
        return helper()
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Codec {
public:
    string serialize(TreeNode* root) {
        string res;
        serializeHelper(root, res);
        return res;
    }
    
    TreeNode* deserialize(string data) {
        int pos = 0;
        return deserializeHelper(data, pos);
    }
    
private:
    void serializeHelper(TreeNode* node, string &res) {
        if (!node) {
            res += "#,";
            return;
        }
        res += to_string(node->val) + ",";
        serializeHelper(node->left, res);
        serializeHelper(node->right, res);
    }
    
    TreeNode* deserializeHelper(const string &data, int &pos) {
        if (pos >= data.size()) return nullptr;
        if (data[pos] == '#') {
            pos += 2;
            return nullptr;
        }
        int next = data.find(',', pos);
        int val = stoi(data.substr(pos, next - pos));
        TreeNode* node = new TreeNode(val);
        pos = next + 1;
        node->left = deserializeHelper(data, pos);
        node->right = deserializeHelper(data, pos);
        return node;
    }
};
      

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

public class Codec {

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }
    
    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }
        sb.append(node.val).append(",");
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }

    public TreeNode deserialize(String data) {
        String[] nodes = data.split(",");
        Index idx = new Index();
        return deserializeHelper(nodes, idx);
    }
    
    private TreeNode deserializeHelper(String[] nodes, Index idx) {
        if (idx.value >= nodes.length || nodes[idx.value].equals("#")) {
            idx.value++;
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(nodes[idx.value++]));
        node.left = deserializeHelper(nodes, idx);
        node.right = deserializeHelper(nodes, idx);
        return node;
    }
    
    private static class Index {
        int value = 0;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var Codec = function() {};

Codec.prototype.serialize = function(root) {
    const vals = [];
    function helper(node) {
        if (!node) {
            vals.push('#');
            return;
        }
        vals.push(node.val.toString());
        helper(node.left);
        helper(node.right);
    }
    helper(root);
    return vals.join(',');
};

Codec.prototype.deserialize = function(data) {
    const vals = data.split(',');
    let idx = 0;
    function helper() {
        if (vals[idx] === '#') {
            idx++;
            return null;
        }
        const node = new TreeNode(parseInt(vals[idx++]));
        node.left = helper();
        node.right = helper();
        return node;
    }
    return helper();
};
      

Problem Description

The "Serialize and Deserialize Binary Tree" problem asks you to design an algorithm to convert a binary tree into a string representation (serialize), and another algorithm to reconstruct the original binary tree from that string (deserialize).

The serialize function should take the root node of a binary tree and return a string that encodes the structure and values of the tree. The deserialize function should take such a string and return the root node of the reconstructed binary tree.

Constraints:

• There is no restriction on the values in the tree nodes (they can be negative, zero, or positive).
• The solution must be stateless: your serialized format should be self-contained, and you cannot store references or global variables.
• The output of serialize must be such that deserialize(serialize(root)) reconstructs the same tree structure and values.

Thought Process

At first glance, the problem is about converting a tree to a string and back without losing any information. The challenge is to ensure that every possible binary tree can be uniquely represented and reconstructed.

A naive approach might be to just write down the node values in order, but this fails for trees with missing children (since you can't tell if a value is a left or right child, or if a child is missing). Thus, we need a way to encode both structure and values.

The key insight is that we can use a traversal (like preorder or level-order) and include special markers (like # or null) for missing children. This way, every position in the string corresponds exactly to a position in the tree, even for empty subtrees.

We move from brute-force (just values) to a robust solution by realizing we must encode structure explicitly. Preorder traversal (root, left, right) with null markers is a natural fit, as it allows us to reconstruct the tree recursively.

Solution Approach

Our approach is to use preorder traversal (visit root, then left subtree, then right subtree) for both serialization and deserialization, marking null children explicitly.

1. Serialization:
   • If the node is null, append a special marker (like # or null) to the output string.
   • If the node exists, append its value, then recursively serialize its left and right children.
   • Join all values (and markers) with a delimiter (like a comma) to form the final string.
2. Deserialization:
   • Split the input string using the delimiter to get a list of values and markers.
   • Use recursion: for each value, if it’s a marker, return null; otherwise, create a node, then recursively build its left and right children from the remaining values.
   • Advance through the list as you reconstruct nodes, matching the original structure.

Why preorder? Because it naturally allows us to reconstruct the tree recursively, as each node is followed by its left and right subtrees in the sequence.

Why use markers for nulls? Without them, you can’t tell where subtrees end or if a child is missing, which would make reconstruction ambiguous.

Example Walkthrough

Let's walk through an example with this binary tree:

        1
       / \
      2   3
         / \
        4   5
  

Serialization:

• Start at root (1): add "1"
• Left child (2): add "2"
• Left child of 2: null, add "#"
• Right child of 2: null, add "#"
• Right child of 1 (3): add "3"
• Left child of 3 (4): add "4"
• Left and right children of 4: both null, add "#", "#"
• Right child of 3 (5): add "5"
• Left and right children of 5: both null, add "#", "#"

The serialized string is: 1,2,#,#,3,4,#,#,5,#,#

• Read "1": create root node 1
• Next "2": create left child 2
• Next "#": left child of 2 is null
• Next "#": right child of 2 is null
• Next "3": right child of 1 is 3
• Next "4": left child of 3 is 4
• Next "#", "#": left and right children of 4 are null
• Next "5": right child of 3 is 5
• Next "#", "#": left and right children of 5 are null

The tree is reconstructed exactly as the original.

Time and Space Complexity

Brute-force Approach: If you tried to just serialize values without structure, it would be O(N) in time, but not correct for all trees.

Optimized Approach (with null markers):

• Time Complexity: O(N), where N is the number of nodes. We visit each node once during serialization and deserialization.
• Space Complexity: O(N), for the serialized string (which stores each node and null marker), and for the recursion stack during (de)serialization (worst-case for a skewed tree).

The null markers mean we have to store information for every node and every missing child, but this is necessary for correctness.

Summary

The key insight for the "Serialize and Deserialize Binary Tree" problem is to explicitly encode both the structure and values of the tree using a traversal (like preorder) and null markers. This allows for unique, stateless reconstruction. The approach is elegant because it’s simple, recursive, and works for all possible binary trees. Both serialization and deserialization are linear in the size of the tree, and the method is widely applicable to tree-based problems.