Serialize and Deserialize Binary Tree

Implement an algorithm to serialize and deserialize a binary tree.

Serialization is the process of converting an in-memory structure into a sequence of bits so that it can be stored or sent across a network to be reconstructed later in another computer environment.

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. There is no additional restriction on how your serialization/deserialization algorithm should work.

Note: The input/output format in the examples is the same as how NeetCode serializes a binary tree. You do not necessarily need to follow this format.

Approach

Use preorder traversal with a sentinel for nulls. Serialize by writing node.val and then its left and right subtrees, using # for null, joined by commas. Deserialize by reading tokens in order and rebuilding the tree recursively. This matches the sample format and handles empty trees.

Why It Works

Preorder with explicit null markers uniquely represents a binary tree structure. During deserialization, each token deterministically reconstructs the same node and subtree boundaries, yielding the original tree.

Complexity

• Time: O(n)
• Space: O(n)

Reference Implementation (Python)

class Codec:
    def serialize(self, root):
        vals = []

        def dfs(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(vals)

    def deserialize(self, data):
        tokens = iter(data.split(','))

        def dfs():
            val = next(tokens)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()