Log inSign up
hardleetcodeNot Started

Serialize and Deserialize Binary Tree

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

Trees
Solve on leetcode
Lesson

Problem Statement

Serialization is the process of 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 tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example 1 · Example 1: Standard Tree:

Input: root = [1, 2, 3, null, null, 4, 5] Tree: 1 / \ 2 3 / \ 4 5
Output: [1, 2, 3, null, null, 4, 5]
Explanation: Tree is encoded into string and reconstructed identically.

Example 2 · Example 2: Empty Tree:

Input: root = []
Output: []
Explanation: Empty tree serializes to null representation.

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -1000 <= Node.val <= 1000

What You'll Learn

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

  • Design reversible data structure serialization formats.
  • Reconstruct binary trees from preorder streams with null markers.
  • Handle string token parsing efficiently.

Pattern Recognition Trigger

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

Signals to Look For:

  • Encode and decode binary tree.
  • Convert tree to string and back to identical tree.
  • System design data serialization.

Algorithmic Decision Tree:

  • Serialize: if !node return #,; return val + , + serialize(left) + serialize(right).
  • Deserialize: pop token; if # return null; else root = new TreeNode(val); root.left = build(); root.right = build().

Connected Patterns:

Construct String from Binary TreeFind Duplicate SubtreesEncode N-ary Tree to Binary Tree

1. Level-Order BFS Serialization with Queue

Intuition

Queue BFS serializes every node or # for null. Deserializer uses a queue to attach children to each parent.

When to apply: When matching LeetCode's array format.

Algorithm

  1. Step 1: Serialize with BFS: append node.val or # to string.
  2. Step 2: Split string by comma.
  3. Step 3: Deserializer uses queue: pop parent, set left = nextToken, right = nextToken.
  4. Step 4: Return root.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Codec {
8public:
9 string serialize(TreeNode* root) {
10 if (!root) return "#";
11 string s = "";
12 queue<TreeNode*> q;
13 q.push(root);
14 while (!q.empty()) {
15 TreeNode* cur = q.front(); q.pop();
16 if (!cur) s += "#,";
17 else {
18 s += to_string(cur->val) + ",";
19 q.push(cur->left);
20 q.push(cur->right);
21 }
22 }
23 return s;
24 }
25 TreeNode* deserialize(string data) {
26 if (data == "#") return nullptr;
27 stringstream ss(data);
28 string item;
29 getline(ss, item, ',');
30 TreeNode* root = new TreeNode(stoi(item));
31 queue<TreeNode*> q;
32 q.push(root);
33 while (!q.empty()) {
34 TreeNode* cur = q.front(); q.pop();
35 if (getline(ss, item, ',')) {
36 if (item != "#") {
37 cur->left = new TreeNode(stoi(item));
38 q.push(cur->left);
39 }
40 }
41 if (getline(ss, item, ',')) {
42 if (item != "#") {
43 cur->right = new TreeNode(stoi(item));
44 q.push(cur->right);
45 }
46 }
47 }
48 return root;
49 }
50};
51
52int main() {
53 // Sample driver execution
54 cout << "Execution completed successfully." << endl;
55 return 0;
56}
57

Time & Space Complexity

  • Time complexity: O(n) — Linear serialization and queue deserialization.
  • Space complexity: O(n) — String and queue hold O(n) elements.

2. Postorder DFS Serialization

Intuition

Postorder serializes left, then right, then root. Deserialization pops from the end of the token list to reconstruct root, right, and left.

When to apply: When using stack/pop from end for parsing.

Algorithm

  1. Step 1: Serialize postorder: left + right + root.
  2. Step 2: Split into array.
  3. Step 3: Pop last token: if #, return null; else root = new TreeNode(val).
  4. Step 4: root.right = build(); root.left = build(). Return root.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Codec {
8 void postorder(TreeNode* root, string& s) {
9 if (!root) { s += "#,"; return; }
10 postorder(root->left, s);
11 postorder(root->right, s);
12 s += to_string(root->val) + ",";
13 }
14 TreeNode* build(vector<string>& tokens) {
15 string val = tokens.back(); tokens.pop_back();
16 if (val == "#") return nullptr;
17 TreeNode* root = new TreeNode(stoi(val));
18 root->right = build(tokens);
19 root->left = build(tokens);
20 return root;
21 }
22public:
23 string serialize(TreeNode* root) {
24 string s = "";
25 postorder(root, s);
26 return s;
27 }
28 TreeNode* deserialize(string data) {
29 stringstream ss(data);
30 string item;
31 vector<string> tokens;
32 while (getline(ss, item, ',')) tokens.push_back(item);
33 return build(tokens);
34 }
35};
36
37int main() {
38 // Sample driver execution
39 cout << "Execution completed successfully." << endl;
40 return 0;
41}
42

Time & Space Complexity

  • Time complexity: O(n) — Single postorder traversal.
  • Space complexity: O(n) — Tokens array takes O(n) space.

3. Preorder DFS with Stream Parsing (Cleanest Code)

Intuition

Preorder serialization: root + , + left + , + right. Deserialization: read next token. If #, return null. Else create root, recurse on left, recurse on right. Return root.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Serialize: if null return #,; return val + , + serialize(left) + serialize(right).
  2. Step 2: Deserializer consumes tokens in FIFO order.
  3. Step 3: Pop token. If #, return null.
  4. Step 4: root = new TreeNode(val). root.left = build(); root.right = build(). Return root.

Serialization & Deserialization Trace for [1, 2, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Serialize tree
Visual state
Values and pointers at this exact step
tree
Root
1
L
2
R
3

Node order shown; add connections to display explicit tree edges.

serial: 1
Check / comparison
String representation created.
Decision / next transition
String ready for transmission.
Why this step matters

Step 1: Serialize tree. 1 -> 2 (leaves #, #) -> 3 (leaves #, #). Output string: 1,2,#,#,3,#,#.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Codec {
8 void serializeDfs(TreeNode* root, string& s) {
9 if (!root) { s += "#,"; return; }
10 s += to_string(root->val) + ",";
11 serializeDfs(root->left, s);
12 serializeDfs(root->right, s);
13 }
14 TreeNode* deserializeDfs(stringstream& ss) {
15 string item;
16 if (!getline(ss, item, ',')) return nullptr;
17 if (item == "#") return nullptr;
18 TreeNode* root = new TreeNode(stoi(item));
19 root->left = deserializeDfs(ss);
20 root->right = deserializeDfs(ss);
21 return root;
22 }
23public:
24 string serialize(TreeNode* root) {
25 string s = "";
26 serializeDfs(root, s);
27 return s;
28 }
29 TreeNode* deserialize(string data) {
30 stringstream ss(data);
31 return deserializeDfs(ss);
32 }
33};
34
35int main() {
36 // Sample driver execution
37 cout << "Execution completed successfully." << endl;
38 return 0;
39}
40

Time & Space Complexity

  • Time complexity: O(n) — Every node processed once in linear time.
  • Space complexity: O(n) — Serialized string and recursion call stack take O(n) space.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BFS Level Order QueueO(n)O(n)Queue holds level by level, matching LeetCode format.Queue indexing.
2.Postorder DFSO(n)O(n)Postorder with reverse pop from end.Reversed ordering.
3.Preorder DFS with StreamOptimalO(n)O(n)Preorder recursive DFS with FIFO token stream.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: serializes to #, deserializes to null.
  • Single node: serializes to 1,#,#.
  • Negative values: string parsing preserves minus sign correctly.

Interview Tips & Best Practices

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

  1. Explain why preorder with null markers uniquely identifies a binary tree (unlike standard preorder which needs inorder).
  2. Mention BFS level-order serialization as a valid alternative that matches LeetCode's bracket representation.

Quick Comprehension Check

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

1.Why is a SINGLE traversal (like Preorder) sufficient to reconstruct a binary tree here, whereas normally both Preorder AND Inorder traversals are required?

Back to DSA Sheet