Serialize and Deserialize Binary Tree

Problem

Serialization is the process of converting a data structure into a sequence of bits (or a string) so that it can be stored or transmitted and reconstructed later. Deserialization is the reverse process — reconstructing the original data structure from the serialized representation.

Your task is to implement two functions:

• serialize(root) — converts a binary tree into a string representation
• deserialize(data) — reconstructs the binary tree from that string

There is no restriction on how your serialization/deserialization algorithm should work. The only guarantee is that deserialize(serialize(root)) must return a tree that is structurally identical with the same node values as the original.

Input / Output Format

serialize(root)

• Input: root — the root node of a binary tree (or null for an empty tree)
• Output: A string representing the serialized tree

deserialize(data)

• Input: data — a string produced by your serialize function
• Output: The root node of the reconstructed binary tree

For testing purposes, trees are provided in level-order (BFS) array format, where null represents a missing node (e.g., [1,2,3,null,null,4,5]).

Examples

Example 1

Input tree (level-order): [1, 2, 3, null, null, 4, 5]

        1
       / \
      2   3
         / \
        4   5

serialize → "1,2,3,null,null,4,5"  (or any valid encoding)
deserialize("1,2,3,null,null,4,5") → reconstructed tree [1,2,3,null,null,4,5]

Explanation: The tree is encoded into a string. After deserialization, we recover the exact same tree structure and values.

Example 2

Input tree (level-order): [1, 2]

    1
   /
  2

serialize → "1,2,null,null,null"
deserialize → reconstructed tree [1,2]

Explanation: Missing children are encoded as null to preserve structure.

Example 3

Input tree: [] (empty tree / null root)

serialize(null) → ""
deserialize("") → null

Explanation: An empty tree serializes to an empty string and deserializes back to null.

Approach Hints

• BFS (Level-Order): Traverse nodes level by level using a queue. Encode null children explicitly. This naturally produces a readable, compact format.
• DFS (Pre-order): Recursively serialize left and right subtrees. Use a sentinel like "#" or "null" for missing nodes. Deserialization uses a pointer/index into the token list.
• Delimiter choice: Use commas or spaces to separate values so they can be split reliably during deserialization.
• Edge cases to consider: Empty tree, single node, trees with only left children (linked-list shape), negative values, and large values.