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 <= 104Problem Overview: Design two functions: serialize converts a Binary Search Tree (BST) into a string, and deserialize reconstructs the same tree from that string. The key constraint is preserving the BST structure so that the reconstructed tree matches the original.
Approach 1: Pre-order Traversal (O(n) time, O(n) space)
This method leverages the properties of a binary search tree. Perform a pre-order traversal (root → left → right) and store node values in sequence. Because BST nodes follow ordering rules, you can rebuild the tree without explicitly storing null markers. During deserialization, read values in order and reconstruct the tree using value bounds. Each recursive call consumes the next valid value that falls within the allowed range. This approach performs a single pass over the nodes, giving O(n) time complexity and O(n) space for the serialized string and recursion stack.
Approach 2: Level-order Traversal (O(n) time, O(n) space)
This approach treats the BST like a general binary tree and uses breadth-first traversal. During serialization, perform a level-order traversal with a queue and append node values to the output string. Include placeholders for missing children so the exact structure can be reconstructed later. During deserialization, read values sequentially and rebuild the tree by assigning left and right children while iterating through the queue. This technique uses a queue and is based on breadth-first search, making it straightforward to implement even if BST ordering properties are ignored. Time complexity remains O(n), and the queue plus serialized data require O(n) space.
Recommended for interviews: The pre-order traversal approach is usually preferred. It takes advantage of BST ordering to avoid storing null markers, producing a more compact serialization. Interviewers often expect candidates to recognize that the BST property allows reconstruction using value ranges with a depth-first search strategy. The level-order method still works and demonstrates solid understanding of tree serialization, but it does not fully utilize the BST constraint.
In 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.
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.
Java
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. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pre-order Traversal with BST Bounds | O(n) | O(n) | Best when leveraging BST properties for compact serialization |
| Level-order Traversal (BFS) | O(n) | O(n) | Useful when treating the tree as a generic binary tree or implementing with queues |
Serialize and Deserialize BST | Leetcode 449 | Recursive DFS | Facebook Amazon Microsoft • Naresh Gupta • 5,063 views views
Watch 9 more video solutions →Practice Serialize and Deserialize BST with our built-in code editor and test cases.
Practice on FleetCode