Serialize and deserialize binary tree
HardSerialization turns a data structure into a string so it can be stored or sent somewhere, and deserialization rebuilds the structure from that string.
Design a Codec class with two methods: serialize(root), which turns a binary tree into a string, and deserialize(data), which turns that string back into an identical tree. You choose the string format. The tests check that deserializing the serialized string rebuilds the original tree, using a separate Codec object for each call.
Trees in the examples and tests are written in level order, with null for a missing child.
Example 1
Input: root = [1, 2, 3, null, null, 4, 5] Output: [1, 2, 3, null, null, 4, 5] 1 / \ 2 3 / \ 4 5
One possible serialization is "1,2,#,#,3,4,#,#,5,#,#", where # marks a missing child.
Example 2
Input: root = [] Output: []
An empty tree has to survive the round trip too.
Constraints
- The tree has between
0and10^4nodes. -1000 <= Node.val <= 1000
Approach
A list of values alone can't describe a tree's shape: [1, 2] and [1, null, 2] have the same values in the same order. Writing a marker for every missing child fixes that. With markers, a pre-order traversal describes exactly one tree, because you always know where each subtree ends.
To serialize, walk the tree in pre-order and write each value, or # for a missing child, separated by commas. To deserialize, split the string and read the values back in the same order with a recursive function. A # returns an empty subtree. Any other value becomes a node, and the function then reads that node's left subtree, followed by its right subtree.
Steps
serialize: visit nodes in pre-order. Append each node's value, or#for an empty child, and join everything with commas.deserialize: split the string on commas and read the pieces in order.- In the reader, return an empty subtree for
#. Otherwise, create a node, then read its left subtree and its right subtree.
Complexity
- Time:
O(n)for each method. Every node and every missing child is written and read once. - Space:
O(n), for the string, plusO(h)for the recursion, wherehis the height of the tree.
Common mistakes
- Leaving out the markers for missing children. Without them,
[1, 2]and[1, null, 2]serialize to the same string. - Joining values without a separator. Multi-digit values become ambiguous:
1,12and11,2would both turn into112.
Related questions
Re-root a binary tree.Delete Node in a Binary Search Tree (BST).Invert binary tree.Related courses




