Design a format to convert a binary tree to a string and rebuild the same tree from that string.
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
datafordeserialize.
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.
Input Format
serialize(root): a binary tree root node.deserialize(data): a string produced byserialize.
Output Format
serialize(root)returns a string encoding of the tree.deserialize(data)returns the root node of the reconstructed tree.
Constraints
- Preserve exact tree structure.
- Null children must be encoded explicitly or otherwise recoverable.
- The solution should be linear in the size of the tree.
- Node values are integers.
Example 1
Input
root = [1,2,3,null,null,4,5]
Output
"1,2,#,#,3,4,#,#,5,#,#"
Explanation
One valid preorder serialization uses # for nulls. Deserializing this string reconstructs the same binary tree.
Example 2
Input
root = []
Output
"#"
Explanation
An empty tree can be represented by a single null marker.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.