Log inSign up
mediumLeetCodeNot Started

Serialize and Deserialize BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

Design an algorithm to serialize and deserialize a Binary Search Tree (BST).

Serialization is converting a tree into a string representation so that it can be stored or transmitted. Deserialization is converting the string back into the original tree structure.

Because the tree is guaranteed to be a BST, you can optimize the encoding to be significantly more compact than general binary tree serialization (e.g., without storing null pointers).

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 valid Binary Search Tree.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Leverage the BST ordering property to eliminate null markers during tree serialization.
  • Reconstruct a BST from preorder values in linear O(N) time using upper-bound constraints.
  • Implement complete standalone serial/deserializer classes across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Serialize and deserialize a Binary Search Tree specifically (not a general tree).
  • Compact encoding requirement without storing null node markers.
  • Reconstruction of BST from sequential traversal.

Algorithmic Decision Tree:

  • If tree is a general Binary Tree -> Preorder with # markers (O(N)).
  • If tree is a BST -> Pure Preorder with boundary checks (O(N) without nulls).

Connected Patterns:

Construct BST from Preorder TraversalSerialize and Deserialize Binary TreeValidate Binary Search Tree

1. Preorder with Null Markers (General Tree Serialization)

Intuition

Traverse the tree in preorder. Append node values followed by a delimiter. For null children, append a special character such as #. Deserialization reads tokens sequentially from a queue: if token is #, return null; otherwise construct node and recurse for left and right children.

When to apply: When treating the BST as a general binary tree without taking advantage of the BST sorted property.

Algorithm

  1. Step 1 (Serialize): DFS preorder; if node is null, append #,; else append val, and recurse left, right.
  2. Step 2 (Deserialize): Split string by commas into a token queue.
  3. Step 3: Define helper: pop token; if # return null; else make TreeNode(token), recurse left and right.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <sstream>
4#include <queue>
5using namespace std;
6
7struct TreeNode {
8 int val;
9 TreeNode *left;
10 TreeNode *right;
11 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12};
13
14class Codec {
15public:
16 void serializeDfs(TreeNode* root, string& out) {
17 if (!root) { out += "#,"; return; }
18 out += to_string(root->val) + ",";
19 serializeDfs(root->left, out);
20 serializeDfs(root->right, out);
21 }
22 string serialize(TreeNode* root) {
23 string out = "";
24 serializeDfs(root, out);
25 return out;
26 }
27 TreeNode* deserializeDfs(queue<string>& q) {
28 if (q.empty()) return nullptr;
29 string token = q.front(); q.pop();
30 if (token == "#") return nullptr;
31 TreeNode* node = new TreeNode(stoi(token));
32 node->left = deserializeDfs(q);
33 node->right = deserializeDfs(q);
34 return node;
35 }
36 TreeNode* deserialize(string data) {
37 queue<string> q;
38 stringstream ss(data);
39 string token;
40 while (getline(ss, token, ',')) {
41 if (!token.empty()) q.push(token);
42 }
43 return deserializeDfs(q);
44 }
45};
46
47int main() {
48 TreeNode* root = new TreeNode(2);
49 root->left = new TreeNode(1);
50 root->right = new TreeNode(3);
51 Codec codec;
52 string serialized = codec.serialize(root);
53 cout << "Serialized: " << serialized << endl;
54 TreeNode* res = codec.deserialize(serialized);
55 cout << "Deserialized Root: " << res->val << endl;
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

2. Preorder Traversal + Binary Search Splitting

Intuition

Store only the preorder sequence of values separated by commas without null markers. To deserialize, the first element is the root. Find the first element greater than root.val: all elements before it belong to the left subtree, and all elements after belong to the right subtree. Recurse on both segments.

When to apply: To save space by omitting null characters, while accepting O(N log N) or O(N2) worst-case deserialize time.

Algorithm

  1. Step 1: Serialize: record preorder sequence of node values without any null markers.
  2. Step 2: Deserialize helper on slice [start, end]: root is arr[start].
  3. Step 3: Binary search for the first index k > start where arr[k] > root.val.
  4. Step 4: Left subtree is [start + 1, k - 1], right subtree is [k, end]. Recurse.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <sstream>
4#include <vector>
5#include <algorithm>
6using namespace std;
7
8struct TreeNode {
9 int val;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13};
14
15class Codec {
16public:
17 void preorder(TreeNode* root, string& s) {
18 if (!root) return;
19 s += to_string(root->val) + " ";
20 preorder(root->left, s);
21 preorder(root->right, s);
22 }
23 string serialize(TreeNode* root) {
24 string s = "";
25 preorder(root, s);
26 return s;
27 }
28 TreeNode* build(const vector<int>& nums, int l, int r) {
29 if (l > r) return nullptr;
30 TreeNode* root = new TreeNode(nums[l]);
31 int idx = upper_bound(nums.begin() + l + 1, nums.begin() + r + 1, nums[l]) - nums.begin();
32 root->left = build(nums, l + 1, idx - 1);
33 root->right = build(nums, idx, r);
34 return root;
35 }
36 TreeNode* deserialize(string data) {
37 stringstream ss(data);
38 vector<int> nums;
39 int val;
40 while (ss >> val) nums.push_back(val);
41 if (nums.empty()) return nullptr;
42 return build(nums, 0, (int)nums.size() - 1);
43 }
44};
45
46int main() {
47 TreeNode* root = new TreeNode(2);
48 root->left = new TreeNode(1);
49 root->right = new TreeNode(3);
50 Codec codec;
51 string serialized = codec.serialize(root);
52 cout << "Serialized: " << serialized << endl;
53 TreeNode* res = codec.deserialize(serialized);
54 cout << "Deserialized Root: " << res->val << endl;
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(N log N) average, O(N^2) worst-case (skewed BST)
  • Space complexity: O(N)

3. Preorder with Value Bound Upper/Lower Limit (O(N) Compact)

Intuition

Serialize using preorder traversal recording only integers. For deserialization, maintain a shared index/pointer into the array and an upper bound limit for the current subtree. If the next value is less than the upper bound, create the node and advance the pointer; recursively build the left child with bound node.val and the right child with bound upper. This takes exactly O(N) time because every value is inspected at most a constant number of times.

When to apply: The industry Gold Standard for BST serialization. Produces the shortest string and reconstructs in single pass O(N) time.

Algorithm

  1. Step 1: Serialize: DFS preorder without nulls, separated by space.
  2. Step 2: Deserialize: Parse numbers into array. Track global pointer idx = 0.
  3. Step 3: Define build(lower, upper): if idx >= length or nums[idx] < lower or nums[idx] > upper, return null.
  4. Step 4: Consume val = nums[idx++]. Create node = TreeNode(val).
  5. Step 5: node.left = build(lower, val) and node.right = build(val, upper). Return node.

Serialize & Deserialize BST Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Root 2 serialized -> '2 1 3'
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Step 1
Why this step matters

Root 2 serialized -> '2 1 3'. On deserialize, root initialized with 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <sstream>
4#include <vector>
5#include <climits>
6using namespace std;
7
8struct TreeNode {
9 int val;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13};
14
15class Codec {
16public:
17 void serializeDfs(TreeNode* root, string& s) {
18 if (!root) return;
19 s += to_string(root->val) + " ";
20 serializeDfs(root->left, s);
21 serializeDfs(root->right, s);
22 }
23 string serialize(TreeNode* root) {
24 string s = "";
25 serializeDfs(root, s);
26 return s;
27 }
28 TreeNode* deserializeDfs(const vector<int>& nums, int& idx, int lower, int upper) {
29 if (idx >= nums.size()) return nullptr;
30 int val = nums[idx];
31 if (val < lower || val > upper) return nullptr;
32 idx++;
33 TreeNode* root = new TreeNode(val);
34 root->left = deserializeDfs(nums, idx, lower, val);
35 root->right = deserializeDfs(nums, idx, val, upper);
36 return root;
37 }
38 TreeNode* deserialize(string data) {
39 stringstream ss(data);
40 vector<int> nums;
41 int val;
42 while (ss >> val) nums.push_back(val);
43 int idx = 0;
44 return deserializeDfs(nums, idx, INT_MIN, INT_MAX);
45 }
46};
47
48int main() {
49 TreeNode* root = new TreeNode(2);
50 root->left = new TreeNode(1);
51 root->right = new TreeNode(3);
52 Codec codec;
53 string serialized = codec.serialize(root);
54 cout << "Optimal Serialized: " << serialized << endl;
55 TreeNode* res = codec.deserialize(serialized);
56 cout << "Optimal Deserialized Root: " << res->val << endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Preorder with Null SentinelsO(N)O(N) (larger string)General tree approach storing # for all null pointers.String memory overhead.
2.Preorder + Binary Search SplitO(N log N) avg, O(N^2) worstO(N) compactStore only values; find left/right boundary using upper_bound.Binary search split finding on unbalanced trees.
3.Preorder with Value BoundsOptimalO(N)O(N) compactReconstruct during a single scan using upper/lower boundary checks.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Including '#' markers when compact BST encoding is asked

Interviewers specifically test whether you realize that BSTs do not need null markers.

Sorting the preorder array to get inorder

While sorting gives inorder traversal and allows construct-from-preorder-inorder in O(N log N), it is slower than the O(N) upper-bound pass.

Global pointer not shared across recursion

When using recursion, the index into the values array must be shared (by reference in C++, nonlocal in Python, or an object in Java) so increments persist across subtree calls.

Crucial Edge Cases to Validate:

  • Empty tree (root == nullptr) — Serializes to empty string ""; deserializes to nullptr.
  • Single node tree — Serializes to single value without delimiters; reconstructs properly.
  • Skewed BST (all left or all right children) — Must not trigger quadratic blowup or stack overflow.
  • Values near boundary constraints (val = 0 or val = 10^4) — Validated correctly against initial INT_MIN and INT_MAX.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the difference immediately: 'General trees need null markers or both preorder and inorder; BSTs only need preorder because BST order implies inorder.'
  2. Explain the O(N) range bounds technique: mirrors the optimal 'Validate BST' recursion in reverse.
  3. Mention that in high-performance network serialization (e.g. Protocol Buffers / Cap'n Proto), integers can be encoded using variable-length varints for even greater compactness.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can a BST be uniquely reconstructed from its Preorder Traversal alone without null markers?

2.What is the primary advantage of the Upper-Bound O(N) deserialization over Binary Search splitting?

3.How much more compact is BST serialization compared to standard binary tree serialization?

Back to DSA Sheet