Serialize and Deserialize Binary Tree
The key idea
A single preorder DFS walk that writes a marker like
# for every empty child captures the full shape of the tree. Because each null is recorded explicitly, the same preorder stream can be consumed token by token to rebuild the exact tree, so serialize and deserialize are mirror images of one walk.Problem
Serialization is the process of turning a data structure into a stream of tokens so it can be stored or sent over a network and then rebuilt later. Deserialization reverses that process. Design an algorithm to serialize a binary tree into a single string and to deserialize that string back into the identical tree. There is no restriction on the format you choose, as long as your own deserializer can read what your serializer wrote and reconstruct the same tree. Each node holds an integer value and references to its left and right children, either of which may be null. Empty children must be preserved so that the rebuilt tree has the same shape, not just the same values.
Constraints
- The number of nodes in the tree is in the range
[0, 10^4]. -1000 <= Node.val <= 1000
Examples
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Input: root = []
Output: []
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY