155. Serialize and Deserialize Binary Tree
🔗 LeetCode Problem: 297. Serialize and Deserialize Binary Tree
📊 Difficulty: Hard
🏷️ Topics: Binary Trees, Serialization, DFS, BFS, String Encoding, Tree Reconstruction
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:
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
🌳 Visual Understanding - What is Serialization?
Concept:
Serialization: Tree → String
Deserialization: String → Tree
Tree:
1
/ \
2 3
/ \
4 5
Serialized (one possible format):
"1,2,null,null,3,4,null,null,5,null,null"
Goal: Perfect round-trip!
Tree → String → Tree (identical!)
Why Serialization?
Use cases:
1. Save tree to file
2. Send tree over network
3. Store tree in database
4. Clone tree structure
5. Compare trees
Must encode structure AND values! 🔑
Key Requirements:
1. Uniqueness
- Different trees → Different strings
- Same tree → Same string
2. Reversibility
- Can reconstruct original tree
- No information loss
3. Efficiency
- Reasonable string length
- Fast encode/decode
This is TREE ENCODING! 🎯
🧠 The AHA Moment - Multiple Approaches!
Approach 1: DFS Preorder (Most Common)
Use preorder traversal:
Root → Left → Right
Tree:
1
/ \
2 3
/ \
4 5
Preorder with nulls:
"1,2,null,null,3,4,null,null,5,null,null"
Why preorder?
- Root first → easy to rebuild
- Natural recursion
- Matches construction order
Approach 2: BFS Level Order
Use level-order traversal:
Level by level
Tree:
1
/ \
2 3
/ \
4 5
Level order:
"1,2,3,null,null,4,5,null,null,null,null"
Why BFS?
- Intuitive structure
- Similar to array representation
- Easier to understand
Visual Comparison:
PREORDER (DFS):
1 → 2 → null → null → 3 → 4 → null → null → 5 → null → null
Depth-first exploration
LEVEL ORDER (BFS):
1 → 2 → 3 → null → null → 4 → 5 → null → null → null → null
Breadth-first exploration
Both work! Different encoding! ✨
🎯 Solution 1: DFS Preorder (Most Elegant)
Why Preorder Works Perfectly:
Preorder = Root, Left, Right
When deserializing:
1. First value = root
2. Next values = left subtree
3. Remaining = right subtree
Natural recursion! 🎯
Implementation:
public class Codec {
private static final String DELIMITER = ",";
private static final String NULL_NODE = "null";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeHelper(root, sb);
return sb.toString();
}
private void serializeHelper(TreeNode node, StringBuilder sb) {
// Base case: null node
if (node == null) {
sb.append(NULL_NODE).append(DELIMITER);
return;
}
// PREORDER: Root → Left → Right
// Step 1: Process root
sb.append(node.val).append(DELIMITER);
// Step 2: Process left subtree
serializeHelper(node.left, sb);
// Step 3: Process right subtree
serializeHelper(node.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
// Split string into tokens
Queue<String> tokens = new LinkedList<>(Arrays.asList(data.split(DELIMITER)));
return deserializeHelper(tokens);
}
private TreeNode deserializeHelper(Queue<String> tokens) {
// Base case: no more tokens or null marker
String val = tokens.poll();
if (val.equals(NULL_NODE)) {
return null;
}
// PREORDER reconstruction: Root → Left → Right
// Step 1: Create root from first token
TreeNode root = new TreeNode(Integer.parseInt(val));
// Step 2: Recursively build left subtree
root.left = deserializeHelper(tokens);
// Step 3: Recursively build right subtree
root.right = deserializeHelper(tokens);
return root;
}
}
Why Queue for Deserialization?
Queue maintains order of tokens:
"1,2,null,null,3,4,null,null,5,null,null"
poll() gives next token in sequence:
First call: "1"
Second call: "2"
etc.
Automatically tracks position! ✨
🔍 Detailed Dry Run - DFS Preorder
Tree:
1
/ \
2 3
/ \
4 5
Serialization (Tree → String):
═══════════════════════════════════════════════════
SERIALIZATION - PREORDER TRAVERSAL
═══════════════════════════════════════════════════
Level 0: serialize(1)
│
├─ node = 1 (not null)
├─ Append: "1,"
│
├─ LEFT: serialize(2) ────────────────────────────┐
│ │
│ Level 1: serialize(2) │
│ │ │
│ ├─ node = 2 (not null) │
│ ├─ Append: "2," │
│ │ │
│ ├─ LEFT: serialize(null) │
│ │ └─ Append: "null," │
│ │ │
│ ├─ RIGHT: serialize(null) │
│ │ └─ Append: "null," │
│ │ │
│ └─ Current string: "1,2,null,null," │
│ │
├─ RIGHT: serialize(3) ───────────────────────────┐
│ │
│ Level 1: serialize(3) │
│ │ │
│ ├─ node = 3 (not null) │
│ ├─ Append: "3," │
│ │ │
│ ├─ LEFT: serialize(4) ──────────────────┐ │
│ │ │ │
│ │ Level 2: serialize(4) │ │
│ │ │ │ │
│ │ ├─ node = 4 (not null) │ │
│ │ ├─ Append: "4," │ │
│ │ │ │ │
│ │ ├─ LEFT: serialize(null) │ │
│ │ │ └─ Append: "null," │ │
│ │ │ │ │
│ │ ├─ RIGHT: serialize(null) │ │
│ │ │ └─ Append: "null," │ │
│ │ │ │ │
│ │ └─ String: "1,2,null,null,3,4,null,null," │
│ │ │ │
│ ├─ RIGHT: serialize(5) ─────────────────┐ │
│ │ │ │
│ │ Level 2: serialize(5) │ │
│ │ │ │ │
│ │ ├─ node = 5 (not null) │ │
│ │ ├─ Append: "5," │ │
│ │ │ │ │
│ │ ├─ LEFT: serialize(null) │ │
│ │ │ └─ Append: "null," │ │
│ │ │ │ │
│ │ ├─ RIGHT: serialize(null) │ │
│ │ │ └─ Append: "null," │ │
│ │ │ │ │
│ │ └─ Final: "1,2,null,null,3,4,null,null,5,null,null,"
│ │ │ │
═══════════════════════════════════════════════════
FINAL STRING: "1,2,null,null,3,4,null,null,5,null,null,"
═══════════════════════════════════════════════════
Deserialization (String → Tree):
═══════════════════════════════════════════════════
DESERIALIZATION - BUILDING TREE
═══════════════════════════════════════════════════
tokens = ["1", "2", "null", "null", "3", "4", "null", "null", "5", "null", "null"]
Level 0: deserialize(tokens)
│
├─ poll() → "1"
├─ Create: TreeNode(1)
│
├─ LEFT: deserialize(tokens) ────────────────────┐
│ │
│ Level 1: deserialize(tokens) │
│ │ │
│ ├─ poll() → "2" │
│ ├─ Create: TreeNode(2) │
│ │ │
│ ├─ LEFT: deserialize(tokens) │
│ │ ├─ poll() → "null" │
│ │ └─ return null │
│ │ │
│ ├─ RIGHT: deserialize(tokens) │
│ │ ├─ poll() → "null" │
│ │ └─ return null │
│ │ │
│ └─ return TreeNode(2) │
│ └─ Tree: 2 │
│ / \ │
│ null null │
│ │
├─ 1.left = TreeNode(2) │
│ │
├─ RIGHT: deserialize(tokens) ───────────────────┐
│ │
│ Level 1: deserialize(tokens) │
│ │ │
│ ├─ poll() → "3" │
│ ├─ Create: TreeNode(3) │
│ │ │
│ ├─ LEFT: deserialize(tokens) ───────────┐ │
│ │ │ │
│ │ Level 2: deserialize(tokens) │ │
│ │ │ │ │
│ │ ├─ poll() → "4" │ │
│ │ ├─ Create: TreeNode(4) │ │
│ │ │ │ │
│ │ ├─ LEFT: poll() → "null" → null │ │
│ │ ├─ RIGHT: poll() → "null" → null │ │
│ │ │ │ │
│ │ └─ return TreeNode(4) │ │
│ │ │ │
│ ├─ 3.left = TreeNode(4) │ │
│ │ │
│ ├─ RIGHT: deserialize(tokens) ──────────┐ │
│ │ │ │
│ │ Level 2: deserialize(tokens) │ │
│ │ │ │ │
│ │ ├─ poll() → "5" │ │
│ │ ├─ Create: TreeNode(5) │ │
│ │ │ │ │
│ │ ├─ LEFT: poll() → "null" → null │ │
│ │ ├─ RIGHT: poll() → "null" → null │ │
│ │ │ │ │
│ │ └─ return TreeNode(5) │ │
│ │ │ │
│ ├─ 3.right = TreeNode(5) │ │
│ │ │
│ └─ return TreeNode(3) │
│ └─ Tree: 3 │
│ / \ │
│ 4 5 │
│ │
├─ 1.right = TreeNode(3) │
│ │
└─ return TreeNode(1) │
└─ Final tree: 1 │
/ \ │
2 3 │
/ \ │
4 5 │
═══════════════════════════════════════════════════
TREE SUCCESSFULLY RECONSTRUCTED! ✓
═══════════════════════════════════════════════════
🎯 Solution 2: BFS Level Order
Implementation:
public class Codec {
private static final String DELIMITER = ",";
private static final String NULL_NODE = "null";
// Encodes a tree to a single string (BFS).
public String serialize(TreeNode root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
sb.append(NULL_NODE).append(DELIMITER);
continue;
}
sb.append(node.val).append(DELIMITER);
queue.offer(node.left); // Can be null
queue.offer(node.right); // Can be null
}
return sb.toString();
}
// Decodes your encoded data to tree (BFS).
public TreeNode deserialize(String data) {
if (data.isEmpty()) return null;
String[] tokens = data.split(DELIMITER);
TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int index = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// Process left child
if (!tokens[index].equals(NULL_NODE)) {
node.left = new TreeNode(Integer.parseInt(tokens[index]));
queue.offer(node.left);
}
index++;
// Process right child
if (!tokens[index].equals(NULL_NODE)) {
node.right = new TreeNode(Integer.parseInt(tokens[index]));
queue.offer(node.right);
}
index++;
}
return root;
}
}
BFS Serialization Example:
Tree:
1
/ \
2 3
/ \
4 5
Level order processing:
Level 0: [1] → "1,"
Level 1: [2, 3] → "2,3,"
Level 2: [null,null,4,5] → "null,null,4,5,"
Level 3: [null,null,null,null] → "null,null,null,null,"
Final: "1,2,3,null,null,4,5,null,null,null,null,"
📊 Complexity Analysis
DFS Preorder:
Time Complexity:
Serialize: O(n)
- Visit each node once
- O(1) work per node
Deserialize: O(n)
- Process each token once
- O(1) work per token
Total: O(n)
Space Complexity:
Serialize: O(n)
- StringBuilder: O(n)
- Recursion stack: O(h)
- Worst: O(n) for skewed tree
Deserialize: O(n)
- Queue for tokens: O(n)
- Recursion stack: O(h)
Total: O(n)
BFS Level Order:
Time Complexity:
Same as DFS: O(n)
Space Complexity:
Serialize: O(n)
- Queue: O(w) where w = max width
- Worst case: O(n) for perfect tree
Deserialize: O(n)
- Queue: O(w)
Total: O(n)
⚠️ Common Mistakes
Mistake 1: Not Encoding Null Nodes
// ❌ WRONG - Only stores non-null values
public String serialize(TreeNode root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
sb.append(root.val).append(",");
sb.append(serialize(root.left));
sb.append(serialize(root.right));
return sb.toString();
}
// Problem: Can't distinguish structure!
// Trees: [1,2,null] and [1,null,2]
// Both give: "1,2," ✗ (same encoding!)
// ✓ CORRECT - Include null markers
if (node == null) {
sb.append("null,");
return;
}
Mistake 2: Wrong Delimiter
// ❌ WRONG - No delimiter
sb.append(node.val); // Just value
// Problem: "12" could be:
// - Nodes 1 and 2
// - Node 12
// Ambiguous! ✗
// ✓ CORRECT - Use delimiter
sb.append(node.val).append(","); ✓
Mistake 3: Not Handling Negative Numbers
// Common oversight: parsing "-10"
// ✓ CORRECT - Integer.parseInt handles negatives
int val = Integer.parseInt(token); ✓
// Works for: "1", "-10", "100", etc.
Mistake 4: Wrong Queue Usage in Deserialization
// ❌ WRONG - Not consuming tokens correctly
private TreeNode deserialize(Queue<String> tokens) {
String val = tokens.peek(); // WRONG! Should poll!
if (val.equals("null")) return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
// tokens not consumed! ✗
}
// ✓ CORRECT - poll() removes from queue
String val = tokens.poll(); ✓
Mistake 5: BFS - Not Handling Null Children in Queue
// ❌ WRONG - Adding nulls to queue
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
queue.offer(node.left); // Might be null!
queue.offer(node.right); // Might be null!
}
// Problem: Can't poll() from null! ✗
// ✓ CORRECT - Check before offering
if (node.left != null) {
queue.offer(node.left); ✓
}
🆚 DFS vs BFS Comparison
Encoding Comparison:
Tree:
1
/ \
2 3
DFS Preorder:
"1,2,null,null,3,null,null"
Depth-first, compact
BFS Level Order:
"1,2,3,null,null,null,null"
Level by level, more nulls at end
Pros and Cons:
DFS PREORDER:
✓ More compact (fewer trailing nulls)
✓ Natural recursion
✓ Elegant code
✓ Matches tree construction pattern
✗ Less intuitive encoding
BFS LEVEL ORDER:
✓ Intuitive (level by level)
✓ Similar to array representation
✓ Easier to visualize
✗ More trailing nulls
✗ Requires queue (no simple recursion)
Both valid! Choose based on preference! ✨
🎯 Pattern Recognition - Serialization Problems
Core Pattern: Encoding Structure
Template for serialization:
serialize(node):
if node == null:
append null marker
return
append node.val
serialize(node.left)
serialize(node.right)
deserialize(tokens):
if next token is null:
return null
node = create from token
node.left = deserialize(tokens)
node.right = deserialize(tokens)
return node
Related Problems:
1. Serialize and Deserialize BST
Similar but can optimize!
BST property allows less info
No need for null markers
2. Encode N-ary Tree to Binary Tree
Different structure transformation
Similar serialization concept
3. String to Integer (atoi)
Similar parsing logic
Handle special cases
String to value conversion
4. Clone Binary Tree
Can use serialization!
Serialize → Deserialize = Clone
When to Use This Pattern:
✓ Need to save/transmit tree
✓ Converting between representations
✓ Cloning with structure
✓ Comparing tree structures
✓ Persistent storage
📝 Quick Revision Notes
🎯 Core Concept
Convert tree to string and back. Use preorder DFS (most elegant): encode as "root,left,right" with null markers. Use Queue in deserialization to consume tokens in order. Alternative: BFS level order (more intuitive but more nulls). Must include null markers to preserve structure. Use delimiter to separate values.
⚡ Quick Implementation (DFS)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
// // Approach 1 - using recursive DFS (preorder)
// // Why preorder than other inorder and postorder? Easy as root comes before for deserialization.
// class Codec {
// String NULL_NODE = "null";
// String DELIMITER = ",";
// // Encodes a tree to a single string.
// public String serialize(TreeNode root) {
// StringBuilder sb = new StringBuilder();
// serializeUtil(root, sb);
// return sb.toString();
// }
// private void serializeUtil(TreeNode root, StringBuilder sb) {
// if(root == null) {
// sb.append(NULL_NODE).append(DELIMITER);
// return;
// }
// sb.append(root.val).append(DELIMITER);
// serializeUtil(root.left, sb);
// serializeUtil(root.right, sb);
// }
// // Decodes your encoded data to tree.
// public TreeNode deserialize(String data) {
// if(data.isEmpty()) {
// return null;
// }
// // When encoded is "1,2,null,null,3,4,null,null,5,null,null," below split handles last , and will not provide any empty string.
// String[] tokens = data.split(DELIMITER);
// // System.out.println(Arrays.toString(tokens));
// // Why Queue? Since this is recursive, polling is best to correctly know the state. Else, messup.
// Queue<String> queue = new LinkedList<>(Arrays.asList(tokens));
// return deserializeUtil(queue);
// }
// private TreeNode deserializeUtil(Queue<String> queue) {
// if(queue.isEmpty()) {
// return null;
// }
// // For below example of (1->2 and 2 has null as both child)
// // Why peek first and then poll?
// // If we poll inside if condition itself, real-data gets lost. So, first check and then poll for null.
// if(queue.peek().equals(NULL_NODE)) {
// queue.poll();
// return null;
// }
// // Same as preorder recursive logic.
// // Retrieve root first.
// TreeNode root = new TreeNode(Integer.valueOf(queue.poll()));
// // construct LST
// // For 1,2,null,null,3,4,null,null,5,null,null,
// // When root with 2 gets initialized/called, below 2 calls for LST and RST are made.
// // As in queue, next 2 values are NULLs, they get polled and returns back here with both root.left and root.right as NULL.
// // So, 2 returns back to 1.left. Now, RST gets started with 3.
// // When we track on paper, it will be clear.
// root.left = deserializeUtil(queue);
// // construct LST
// root.right = deserializeUtil(queue);
// return root;
// }
// }
// Approach 2 - using iterative BFS
class Codec {
String NULL_NODE = "null";
String DELIMITER = ",";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if(root == null) {
return sb.append(NULL_NODE).append(DELIMITER).toString();
}
// Normal BFS (with extra StringBuilder to create the encoded string).
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
if(curr == null) {
sb.append(NULL_NODE).append(DELIMITER).toString();
continue;
}
sb.append(curr.val).append(DELIMITER);
queue.add(curr.left); // CHANGE. Normally, we put a branch for NULL check and add to queue.
queue.add(curr.right); // CHANGE. Normally, we put a branch for NULL check and add to queue.
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.isEmpty()) {
return null;
}
// When encoded is "1,2,null,null,3,4,null,null,5,null,null," below split handles last , and will not provide any empty string.
String[] tokens = data.split(DELIMITER);
if(tokens == null || tokens.length == 0 || tokens[0].equals(NULL_NODE)) {
return null;
}
// System.out.println(Arrays.toString(tokens));
int i = 0; // lets start with root.
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.valueOf(tokens[i]));
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode curr = queue.poll();
i++; // retrieving next token which can be number or null.
String nextToken = tokens[i];
// In case of 1,2,3,null,null,4,5,null,null,null,null,
// when curr is 1, 2 is nextToken and curr.left gets formed.
// when curr is 2, null is nextToken and curr.left gets null and no need to add in queue.
if(nextToken.equals(NULL_NODE)) {
curr.left = null;
} else {
curr.left = new TreeNode(Integer.valueOf(nextToken));
queue.offer(curr.left);
}
i++; // retrieving next token which can be number or null.
nextToken = tokens[i];
if(nextToken.equals(NULL_NODE)) {
curr.right = null;
} else {
curr.right = new TreeNode(Integer.valueOf(nextToken));
queue.offer(curr.right);
}
}
return root;
}
}
public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
Codec c = new Codec();
String encoded = c.serialize(TreeNode.buildTree(new Integer[] {1,2,3,null,null,4,5}));
// In case of DFS: 1,2,null,null,3,4,null,null,5,null,null,
// In case of BFS: 1,2,3,null,null,4,5,null,null,null,null,
System.out.println("Encoded: "+encoded);
TreeNode.print(c.deserialize(encoded)); // [1, 2, 3, null, null, 4, 5]
}
}
🔑 Key Insights
Why Preorder Works:
Preorder = Root, Left, Right
Matches construction order:
1. Create root (first value)
2. Build left subtree (next values)
3. Build right subtree (remaining)
Natural for recursion! 🔑
Queue for Token Consumption:
Without queue:
Need index tracking
Pass index around
More complex
With queue:
poll() automatically advances
Clean, simple
No index management
Queue is perfect data structure! ✨
Why Null Markers Essential:
Without nulls:
[1,2] and [1,null,2] both → "1,2"
Can't distinguish structure! ✗
With nulls:
[1,2] → "1,2,null,null,null"
[1,null,2] → "1,null,2,null,null"
Different encodings! ✓
Nulls encode structure! 🎯
Delimiter Necessity:
Without delimiter:
"121" could be:
- Nodes 1, 2, 1
- Nodes 12, 1
- Node 121
Ambiguous! ✗
With delimiter:
"1,2,1" → clearly three nodes ✓
"12,1" → clearly two nodes ✓
Delimiter removes ambiguity! 🔑
🎪 Memory Aid
"Preorder: Root → Left → Right!"
"Include null markers (structure!)!"
"Use queue to consume tokens!"
"Delimiter separates values!" ✨
⚠️ Don't Forget
- Include null markers (preserve structure!)
- Use delimiter (",")
- Queue.poll() (consume tokens!)
- Preorder for serialize (Root, Left, Right!)
- Same order for deserialize (build in preorder!)
- Handle negative numbers (Integer.parseInt!)
🎉 Congratulations!
You've mastered tree serialization!
What You Learned:
✅ Serialization concept - Tree to string
✅ DFS preorder - Most elegant approach
✅ BFS level order - Alternative method
✅ Null markers - Structure preservation
✅ Queue usage - Token consumption
✅ Round-trip - Perfect reconstruction
The Elegant Design:
Preorder serialization is BEAUTIFUL because:
1. Natural order (Root → Left → Right)
2. Matches construction pattern
3. Clean recursion
4. Automatic token consumption with queue
5. Perfect round-trip guarantee
Industry standard approach! ✨
Interview Mastery:
Interviewer: "Serialize and deserialize binary tree"
Your response:
"Use preorder DFS for elegance.
Serialize:
- Preorder traversal
- Append nulls for structure
- Use delimiter
Deserialize:
- Queue for tokens
- Build in preorder
- poll() consumes automatically
Alternative: BFS level order
(more intuitive but more nulls)
Time: O(n), Space: O(n)"
Shows complete understanding! 💯
You've learned a fundamental technique used in databases, networks, and storage systems! 🏆✨🎯