Watch 10 video solutions for Serialize and Deserialize BST, a medium level problem involving String, Tree, Depth-First Search. This walkthrough by Naresh Gupta has 5,063 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |