Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Example 1:
Input: root = [2,1,3] Output: [2,1,3]
Example 2:
Input: root = [] Output: []
Constraints:
[0, 104].0 <= Node.val <= 104In this approach, we utilize pre-order traversal (Root-Left-Right) to serialize the BST. The serialized string will be a space-separated string that represents the order of visiting nodes during pre-order traversal.
During deserialization, you use the properties of the pre-order traversal and BST to reconstruct the tree. The key is to maintain the order of insertions such that it respects BST properties.
The serialize function performs a pre-order traversal to create a space-separated string of node values. The deserialize function reads from this string (reversed) and reconstructs the tree by checking the constraints for valid BST nodes, creating a tree using bounds for node values as it progresses.
C++
Time Complexity: O(n) for both serialization and deserialization, where n is the number of nodes.
Space Complexity: O(n) for storing the serialized data.
Level-order traversal (BFS) involves visiting each level of the tree one at a time, which can be used to serialize the tree into a compact form. For empty positions, we can indicate using a special character (e.g., '#'). This method guarantees that we record the full structure of the tree including missing nodes.
This Java solution serialized the BST using a level-order traversal, noting nulls for missing children. During deserialization, nodes are reconstructed level by level, keeping track of parents and appending appropriate left and right children.
JavaScript
Time Complexity: O(n) for both serialization and deserialization.
Space Complexity: O(n) due to the queue usage in both processes.
| Approach | Complexity |
|---|---|
| Approach 1: Pre-order Traversal | Time Complexity: O(n) for both serialization and deserialization, where n is the number of nodes. |
| Approach 2: Level-order Traversal | Time Complexity: O(n) for both serialization and deserialization. |
L36. Serialize and De-serialize Binary Tree | C++ | Java • take U forward • 175,648 views views
Watch 9 more video solutions →Practice Serialize and Deserialize BST with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor