Serialize and Deserialize BST
Medium · Trees · String · Tree · Depth-First Search · Breadth-First Search · Design · Binary Search Tree · Binary Tree
Problem
Design an algorithm that turns a binary search tree into a string (serialization) and turns that string back into the same tree (deserialization).
Implement a Codec with serialize(root), which returns a string, and deserialize(data), which returns the root of a tree. You may choose any string format, but deserialize(serialize(root)) must reproduce the original tree. The codec must keep no state: the string is decoded by a fresh Codec.
Keep the string as compact as possible. The BST ordering lets you drop information a general binary tree would need, such as markers for missing children.
The values in the tree are distinct. In the examples, the output is the tree you get back after a round trip, in level order.
Examples
Input: root = [7,3,11,1,5] Output: [7,3,11,1,5]
A preorder string such as "7,3,1,5,11" is enough to rebuild this BST exactly.
Input: root = [] Output: []
An empty tree becomes an empty string and comes back empty.
Input: root = [2,None,4,None,6] Output: [2,None,4,None,6]
Preorder "2,4,6": each value is larger than everything before it, so each goes right.
Constraints
- The number of nodes is in the range [0, 10^4]
- 0 <= Node.val <= 10^4, all distinct
- The input tree is a binary search tree
Approaches
- Baseline: preorder values, decode by inserting — time O(n · h), O(n²) for a chain, space O(n)
Follow-up
Preorder values alone are enough, so the string holds just n numbers and n - 1 separators. A fixed-width binary encoding (two bytes per value here) would be shorter still. The use cases rebuild a BST from a second compact format, level order without gaps, and decide whether two insertion orders build the same BST.
Related problems
Start free on Cariara · Coding problems · System design studio
