Serialize and Deserialize Binary Tree
LeetCode 297 | Difficulty: Hard
HardProblem Description
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.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Example 2:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range `[0, 10^4]`.
- `-1000 <= Node.val <= 1000`
Topics: String, Tree, Depth-First Search, Breadth-First Search, Design, Binary Tree
Approach
Tree DFS
Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.
Path problems, subtree properties, tree structure manipulation.
Tree BFS (Level-Order)
Use a queue to process the tree level by level. At each level, process all nodes in the queue, then add their children. Track the level size to know when one level ends and the next begins.
Level-order traversal, level-based aggregation, right/left side view.
Design
Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.
Implementing a data structure or system with specific operation time requirements.
String Processing
Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.
Anagram detection, palindrome checking, string transformation, pattern matching.
Solutions
Solution 1: C# (Best: 111 ms)
| Metric | Value |
|---|---|
| Runtime | 111 ms |
| Memory | 42 MB |
| Date | 2022-01-12 |
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Codec {
public string serialize(TreeNode root)
{
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.ToString();
}
private void serializeBST(TreeNode root, StringBuilder sb)
{
if (root == null)
{
return;
}
sb.Append($"{root.val},");
serializeBST(root.left, sb);
serializeBST(root.right, sb);
}
private void serialize(TreeNode root, StringBuilder sb)
{
if (root == null)
{
sb.Append("#,");
return;
}
sb.Append($"{root.val},");
serialize(root.left, sb);
serialize(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(string data)
{
Queue<string> q = new Queue<string>(data.Split(new char[] { ','}, StringSplitOptions.RemoveEmptyEntries));
return deserialize(q);
}
public TreeNode deserialize(Queue<string> q, int lower, int upper)
{
if(q.Count == 0) return null;
var val = Convert.ToInt32(q.Peek());
if(val < lower || val > upper) return null;
q.Dequeue();
TreeNode root = new TreeNode(val);
root.left = deserialize(q, lower, val);
root.right = deserialize(q, val, upper);
return root;
}
public TreeNode deserialize(Queue<string> q)
{
if(q.Count ==0 ) return null;
var popped = q.Dequeue();
if(popped == "#") return null;
TreeNode root = new TreeNode(Convert.ToInt32(popped));
root.left = deserialize(q);
root.right = deserialize(q);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
📜 2 more C# submission(s)
Submission (2019-12-15) — 128 ms, 32.9 MB
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Codec {
public string serialize(TreeNode root)
{
if (root == null) return null;
Queue<TreeNode> q = new Queue<TreeNode>();
StringBuilder sb = new StringBuilder();
q.Enqueue(root);
while (q.Count != 0)
{
var node = q.Dequeue();
if (node == null)
{
sb.Append("null,");
}
else
{
sb.Append($"{node.val},");
q.Enqueue(node.left);
q.Enqueue(node.right);
}
}
return sb.ToString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(string data)
{
if (string.IsNullOrEmpty(data))
{
return null;
}
Queue<TreeNode> q = new Queue<TreeNode>();
var nodes = data.Split(new char[] { ',' },StringSplitOptions.RemoveEmptyEntries);
TreeNode root = new TreeNode(Convert.ToInt32(nodes[0]));
q.Enqueue(root);
for (int i = 1; i < nodes.Length; i++)
{
var parent = q.Dequeue();
if (nodes[i] != "null")
{
var left = new TreeNode(Convert.ToInt32(nodes[i]));
parent.left = left;
q.Enqueue(left);
}
i++;
if (nodes[i] != "null")
{
var right = new TreeNode(Convert.ToInt32(nodes[i]));
parent.right = right;
q.Enqueue(right);
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
Submission (2019-12-12) — 132 ms, 33.4 MB
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Codec {
public string serialize(TreeNode root)
{
if (root == null) return null;
Queue<TreeNode> q = new Queue<TreeNode>();
StringBuilder sb = new StringBuilder();
q.Enqueue(root);
while (q.Count != 0)
{
var node = q.Dequeue();
if (node == null)
{
sb.Append("null,");
}
else
{
sb.Append($"{node.val},");
q.Enqueue(node.left);
q.Enqueue(node.right);
}
}
return sb.ToString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(string data)
{
if (string.IsNullOrEmpty(data))
{
return null;
}
Queue<TreeNode> q = new Queue<TreeNode>();
var nodes = data.Split(new char[] { ',' },StringSplitOptions.RemoveEmptyEntries);
TreeNode root = new TreeNode(Convert.ToInt32(nodes[0]));
q.Enqueue(root);
for (int i = 1; i < nodes.Length; i++)
{
var parent = q.Dequeue();
if (nodes[i] != "null")
{
var left = new TreeNode(Convert.ToInt32(nodes[i]));
parent.left = left;
q.Enqueue(left);
}
i++;
if (nodes[i] != "null")
{
var right = new TreeNode(Convert.ToInt32(nodes[i]));
parent.right = right;
q.Enqueue(right);
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| Tree Traversal | $O(n)$ | $O(h)$ |
Interview Tips
- Break the problem into smaller subproblems. Communicate your approach before coding.
- Consider: "What information do I need from each subtree?" — this defines your recursive return value.
- Clarify the expected time complexity for each operation before choosing data structures.