Serialize and Deserialize Binary Tree
Problem
Design an algorithm to serialize a binary tree into a string and deserialize the string back to the original binary tree structure.
- The number of nodes in the tree is in the range [0, 10⁴]
- −1000 ≤ Node.val ≤ 1000
Example
root = [1,2,3,null,null,4,5]"1,2,N,N,3,4,N,N,5,N,N"The serialization uses preorder traversal with 'N' representing null nodes. For the example tree, the traversal visits node 1, then left subtree (2 with null children), then right subtree (3 with children 4 and 5). The serialized string captures this structure. During deserialization, the string is split and recursively parsed to rebuild the exact tree shape by consuming values in preorder and interpreting 'N' as null nodes.
Approach
Straightforward Solution
A naive approach might serialize only node values without null markers, which leads to ambiguity during deserialization because the tree shape cannot be inferred from values alone.
Core Observation
A binary tree can be uniquely represented by a preorder traversal that includes markers for null children. This ensures that the structure and values are fully captured in a linear string.
Path to Optimal
PreviewThe key insight is to include explicit null markers ('N') during preorder traversal. This transforms the tree into a sequence where each node and its subtree boundaries are clearly defined…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a recursive DFS preorder traversal to serialize the tree, appending 'N' for null nodes. For deserialization, split the string by commas and recursively build the tree by consuming values in order, creating nodes or returning null when encountering 'N'…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Both serialization and deserialization visit each node exactly once in preorder, performing constant work per node.
Space
O(n)
The recursion stack and the serialized string both scale linearly with the number of nodes, as each node and null child is represented explicitly.
Pattern Spotlight
DFS (Preorder Traversal with State Preservation)
When serializing and deserializing trees, use preorder traversal with explicit null markers to preserve structure, enabling a recursive reconstruction that consumes the serialized data in the same order it was produced.
Solution
| 1 | class Codec:
|
| 2 |
|
| 3 | def serialize(self, root):
|
| 4 | res = []
|
| 5 |
|
| 6 | def dfs(node):
|
| 7 | if not node:
|
| 8 | res.append("N")
|
| 9 | return
|
| 10 | res.append(str(node.val))
|
| 11 | dfs(node.left)
|
| 12 | dfs(node.right)
|
| 13 |
|
| 14 | dfs(root)
|
| 15 | return ",".join(res)
|
| 16 |
|
| 17 | def deserialize(self, data):
|
| 18 | vals = data.split(',')
|
| 19 | self.i = 0
|
| 20 |
|
| 21 | def dfs():
|
| 22 | if vals[self.i] == "N":
|
| 23 | self.i += 1
|
| 24 | return None
|
| 25 |
|
| 26 | node = TreeNode(int(vals[self.i]))
|
| 27 | self.i += 1
|
| 28 | node.left = dfs()
|
| 29 | node.right = dfs()
|
| 30 | return node
|
| 31 |
|
| 32 | return dfs() |
Step-by-Step Solution
Serialize Tree Using Preorder DFS with Null Markers
| 3 | def serialize(self, root):
|
| 4 | res = []
|
| 6 | def dfs(node):
|
| 7 | if not node:
|
| 8 | res.append("N")
|
| 9 | return
|
| 10 | res.append(str(node.val))
|
| 11 | dfs(node.left)
|
| 12 | dfs(node.right)
|
| 14 | dfs(root)
|
| 15 | return ",".join(res)
|
Objective
To convert the binary tree into a string by recursively traversing it in preorder and recording node values and nulls.
Key Insight
Preorder traversal naturally captures the root before its subtrees, which aligns with the recursive deserialization process. Including 'N' for null children ensures that the serialized string encodes the exact tree shape, allowing unambiguous reconstruction. The recursion appends values or 'N' to a list, which is joined into a comma-separated string at the end.
Interview Quick-Check
Core Logic
The preorder traversal with explicit null markers encodes both node values and tree structure, enabling perfect reconstruction.
State & Boundaries
The base case appends 'N' for null nodes, marking leaf boundaries.
Common Pitfalls & Bugs
Omitting null markers leads to ambiguous serialization that cannot be deserialized correctly.
Deserialize String Back to Tree Using Recursive DFS
To reconstruct the binary tree by recursively consuming the serialized string tokens in preorder, creating nodes or returning null as indicated.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
res.append("N")Append the null marker 'N' to the serialization list.
This line is critical because it encodes the absence of a node, which is necessary to reconstruct the exact tree shape during deserialization.
if vals[self.i] == "N":Check if the current token is the null marker 'N'.
This check is critical because it determines when to stop recursion and correctly represent null children, preserving the tree's shape.
Full line-by-line criticality + rationale for all 24 lines available on Pro.
Test Your Understanding
Why is it necessary to include explicit null markers during serialization?
See the answer with Pro.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Serialize and Deserialize Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Serialize and Deserialize Binary Tree drill