DSA problem
Serialize and Deserialize Binary Tree
Design an algorithm to serialize and deserialize a binary tree. Serialization converts a tree into a string so it can be stored to disk or sent across a network; deserialization reconstructs the original tree from that string. The output string must uniquely identify the tree, including its shape (the positions of null children).
The classic approach uses preorder traversal with explicit null markers. During serialization, we visit each node in root-left-right order. For a non-null node we write its value; for a null pointer we write a sentinel such as "#". We separate tokens with a delimiter like ,. The trailing nulls at the leaves are what make this representation unambiguous — without them, multiple distinct trees could produce the same value sequence.
Deserialization is the mirror image. We split the string on the delimiter and walk through the tokens with a shared index. If the next token is "#" return null; otherwise create a node with that value, then recursively assign node.left and node.right. Because the tokens were emitted in preorder, consuming them in order via a single shared cursor reconstructs the exact same tree.
This problem is implemented as a Codec class with two methods: serialize(root) → string and deserialize(data) → root. Both run in O(n) time where n is the number of nodes; serialization produces O(n) characters of output, and deserialization uses O(h) stack space. The same problem appears under several variants (BFS with nulls, parentheses-style, etc.), but the preorder approach is the most concise and the most common interview answer.
Examples
root = [1,2,3,null,null,4,5]"1,2,#,#,3,4,#,#,5,#,#"root = []"#"root = [1]"1,#,#"Constraints
- The number of nodes in the tree is in the range [0, 10^4].
- -1000 <= Node.val <= 1000
- The serialized format is your choice as long as deserialize(serialize(root)) reproduces the original tree.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.