Problem

Given the root of a binary tree, design two functions:

• serialize(root): convert the tree into a string representation.
• deserialize(data): rebuild the exact same binary tree from that string.

Your serialization must preserve the tree structure, including missing children. Any valid encoding is acceptable as long as deserialize(serialize(root)) produces a tree equivalent to the original.

Notes

• The tree may be empty.
• Node values are integers.
• You should be able to handle both balanced and highly skewed trees.
• The order of nodes in the string is up to you, but the encoding must be unambiguous.

Input Format

• A binary tree root for serialize.
• A string data for deserialize.

Output Format

• serialize(root) returns a string.
• deserialize(data) returns the root of the reconstructed binary tree.

Constraints

• The tree can contain null children at arbitrary positions.
• The encoding should be reversible.
• Aim for linear time relative to the number of nodes.

Hints

• Use placeholders for missing nodes so the tree shape can be recovered.
• Preorder or level-order traversal are both common choices.
• Think carefully about how to separate values in the output string so parsing stays simple.