Serialize and Deserialize BST - Solution & Explanation
Problem Statement
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:
- The number of nodes in the tree is in the range
[0, 104]. 0 <= Node.val <= 104- The input tree is guaranteed to be a binary search tree.
Approach Overview
Problem 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.
Approach 1: Approach 1: Pre-order Traversal
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.
Complexity
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.
Approach 2: Approach 2: Level-order Traversal
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.
Code
Java
JavaScript
Complexity
Time Complexity: O(n) for both serialization and deserialization.
Space Complexity: O(n) due to the queue usage in both processes.
Approach 3: Default Approach
Try this approach in the editor βComplexity Comparison
| 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 | β |
Detailed Complexity Analysis
| 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 |
Video Solution
θ±θ±ι ± LeetCode 449. Serialize and Deserialize BST - ε·ι’ζΎε·₯δ½ EP91 β’ Hua Hua β’ 8,059 views views
Watch 9 more video solutions βFrequently Asked Questions
Is Serialize and Deserialize BST easy or hard?
Serialize and Deserialize BST Python/Java solution
How to solve Serialize and Deserialize BST in O(n)?
What is the best approach for Serialize and Deserialize BST?
Is Serialize and Deserialize BST asked at Google/Amazon/Meta?
What data structure is used in Serialize and Deserialize BST?
What is the time complexity of Serialize and Deserialize BST?
Ready to solve this problem?
Practice Serialize and Deserialize BST with our built-in code editor and test cases.
Practice on FleetCode