Serialize and Deserialize Binary Tree
Mahabharata — The Sacred Inscription — Encode the Entire Tree as a String, Then Restore It
वृक्ष को लिखो — N शून्य के लिए। Pre-order से पढ़ो — वापस बनाओ॥
*Write the tree — N for null. Read with preorder — reconstruct it.*
The Story
Design an algorithm to serialize (encode) a binary tree to a string and deserialize (decode) back from the string.
For tree `[1,2,3,null,null,4,5]`: serialize might give `"1,2,N,N,3,4,N,N,5,N,N"` (preorder with null markers). Deserializing that string reconstructs the original tree.
**Preorder serialization with 'N' for null:** ```java public String serialize(TreeNode root) { if (root == null) return "N"; return root.val + "," + serialize(root.left) + "," + serialize(root.right); } ```
**Deserialization with a queue of tokens:** ```java public TreeNode deserialize(String data) { Queue<String> q = new LinkedList<>(Arrays.asList(data.split(","))); return build(q); } TreeNode build(Queue<String> q) { String token = q.poll(); if (token.equals("N")) return null; TreeNode node = new TreeNode(Integer.parseInt(token)); node.left = build(q); // Process left subtree node.right = build(q); // Then right subtree return node; } ```
The queue maintains the position in the serialized string. Each call to `build()` consumes exactly the tokens for one subtree in preorder.
Trace serialize `[1,2,3]`: - serialize(1): "1," + serialize(2) + serialize(3) - serialize(2): "2,N,N" - serialize(3): "3,N,N" - Result: "1,2,N,N,3,N,N"
Deserialize "1,2,N,N,3,N,N": - q=["1","2","N","N","3","N","N"] - build(): poll "1" → node(1). node.left=build(): - poll "2" → node(2). node.left=build(): - poll "N" → null - node.right=build(): - poll "N" → null - return node(2) - node.right=build(): - poll "3" → node(3). null left, null right. - return node(1) — tree [1,2,3] ✓
The BFS Level-Order Serialization
BFS with null markers. Same approach used by LeetCode's tree display format. O(n) but wider format.
// BFS serialize:
String serializeBFS(TreeNode root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> q = new LinkedList<>(); q.offer(root);
while (!q.isEmpty()) {
TreeNode n = q.poll();
if (n==null) { sb.append("N,"); continue; }
sb.append(n.val).append(',');
q.offer(n.left); q.offer(n.right);
}
return sb.toString();
}The Preorder + N-Sentinel Wisdom
public String serialize(TreeNode root) {
if (root == null) return "N";
return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
public TreeNode deserialize(String data) {
Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
return build(q);
}
TreeNode build(Queue<String> q) {
String token = q.poll();
if ("N".equals(token)) return null;
TreeNode node = new TreeNode(Integer.parseInt(token));
node.left = build(q);
node.right = build(q);
return node;
}Step-by-Step Walkthrough
Null tree: serialize=null→"N". deserialize("N"): poll "N" → return null. ✅
Single [1]: serialize="1,N,N". deserialize: poll "1"→node(1). left=poll "N"→null. right=poll "N"→null. Return 1. ✅Deep Insight
**Why preorder works for serialization:** Preorder visits root before children. During deserialization, when we read a value, we create the node immediately, then read its left and right subtrees in order. The queue ensures we consume tokens in the exact preorder sequence.
**The queue trick:** Instead of an index counter, using a Queue allows each recursive call to `build()` to consume its own tokens and return, leaving the queue at the right position for subsequent calls. This is cleaner than passing an int[] index.
**Why 'N' not "null"?** Shorter representation. Any unique sentinel works.
**BFS serialization:** The BFS approach matches LeetCode's tree format (e.g., [1,2,3,null,null,4,5]). The preorder approach is simpler to implement recursively.
**This is the FINAL Tree problem in the collection!** Serialize/Deserialize represents the complete lifecycle of a tree — creation, encoding, transmission, and reconstruction.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | BFS with null markers |
| Optimal | O(n) | O(n) | Preorder DFS; O(n) string; O(n) queue |
Pattern Recognition
✅ Serialize: preorder with 'N' for null ✅ Deserialize: queue of tokens, poll per build() call ✅ Recursive preorder reconstruction with queue ✅ Any order works (preorder, BFS) with appropriate deserializer **LeetCode Trigger Phrases:** → "serialize and deserialize binary tree" → Encode tree to string and reconstruct → DFS preorder with null sentinel
Bhagavad Gita 14.2
इदं ज्ञानमुपाश्रित्य मम साधर्म्यमागताः। सर्गेऽपि नोपजायन्ते प्रलये न व्यथन्ति च॥
Taking refuge in this knowledge and attaining similarity with Me — they are not born again even at the time of creation, nor disturbed at the time of dissolution.
Connection: Serialization encodes the tree's complete essence into a string — preserving it through any medium (disk, network, memory). Deserialization reconstructs it perfectly from that encoding. Like the knowledge that transcends creation and dissolution (the tree persists through serialization and restoration), the algorithm ensures no information is lost. The null markers preserve the exact shape, the values preserve the content — together they capture the complete and imperishable truth of the tree's structure.