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
The 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. During deserialization, the sequence can be consumed in order, reconstructing the tree by interpreting 'N' as leaf terminations. This approach leverages the recursive nature of preorder traversal to serialize and deserialize symmetrically.
Optimal Approach
Use 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'. This guarantees O(n) time and space complexity, where n is the number of nodes.
Time
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() |
| 1 | class Codec { |
| 2 | public String serialize(TreeNode root) { |
| 3 | List<String> res = new ArrayList<>(); |
| 4 | dfsSerialize(root, res); |
| 5 | return String.join(",", res); |
| 6 | } |
| 7 | |
| 8 | private void dfsSerialize(TreeNode node, List<String> res) { |
| 9 | if (node == null) { |
| 10 | res.add("N"); |
| 11 | return; |
| 12 | } |
| 13 | res.add(String.valueOf(node.val)); |
| 14 | dfsSerialize(node.left, res); |
| 15 | dfsSerialize(node.right, res); |
| 16 | } |
| 17 | |
| 18 | public TreeNode deserialize(String data) { |
| 19 | String[] vals = data.split(","); |
| 20 | int[] index = new int[1]; |
| 21 | return dfsDeserialize(vals, index); |
| 22 | } |
| 23 | |
| 24 | private TreeNode dfsDeserialize(String[] vals, int[] index) { |
| 25 | if (vals[index[0]].equals("N")) { |
| 26 | index[0]++; |
| 27 | return null; |
| 28 | } |
| 29 | |
| 30 | TreeNode node = new TreeNode(Integer.parseInt(vals[index[0]])); |
| 31 | index[0]++; |
| 32 | node.left = dfsDeserialize(vals, index); |
| 33 | node.right = dfsDeserialize(vals, index); |
| 34 | return node; |
| 35 | } |
| 36 | } |
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
| 17 | def deserialize(self, data):
|
| 18 | vals = data.split(',')
|
| 19 | self.i = 0
|
| 21 | def dfs():
|
| 22 | if vals[self.i] == "N":
|
| 23 | self.i += 1
|
| 24 | return None
|
| 26 | node = TreeNode(int(vals[self.i]))
|
| 27 | self.i += 1
|
| 28 | node.left = dfs()
|
| 29 | node.right = dfs()
|
| 30 | return node
|
| 32 | return dfs() |
Objective
To reconstruct the binary tree by recursively consuming the serialized string tokens in preorder, creating nodes or returning null as indicated.
Key Insight
Deserialization mirrors serialization by reading tokens in order. When encountering 'N', it returns null, signaling leaf boundaries. For numeric tokens, it creates a node and recursively builds left and right subtrees. Using an index pointer to track the current token ensures the recursion consumes tokens sequentially without losing state. This approach guarantees the tree is rebuilt exactly as serialized.
Interview Quick-Check
Core Logic
The recursive deserialization consumes tokens in preorder, using 'N' to identify null nodes and reconstructing the tree structure exactly.
State & Boundaries
The index pointer advances with each token consumed, preserving the correct position in the serialized data.
Common Pitfalls & Bugs
Failing to increment the index after processing a token leads to infinite recursion or incorrect tree structure.
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.
if not node:Check if the current node is null.
Detecting null nodes is essential to append the null marker and terminate recursion on leaf branches.
res.append(str(node.val))Append the string value of the current node to the serialization list.
Recording node values in preorder ensures the serialized string captures the tree's data and traversal order.
self.i = 0Initialize an index pointer to track the current token during deserialization.
Maintaining a pointer allows the recursive function to consume tokens in order without losing position.
self.i += 1Increment the index pointer after processing a null token.
Advancing the pointer ensures the next recursive call processes the subsequent token, maintaining correct traversal order.
node = TreeNode(int(vals[self.i]))Create a new tree node with the integer value of the current token.
Constructing a node from the token value rebuilds the tree's data at the correct position.
self.i += 1Increment the index pointer after consuming a node value.
Moving the pointer forward ensures the recursive calls process tokens in the correct sequence.
res = []Initialize a list to accumulate serialized node values and null markers.
Using a list to collect values during traversal is efficient and allows easy joining into a final string, avoiding costly string concatenations.
returnReturn from the recursion when a null node is encountered.
Stopping recursion at null nodes prevents unnecessary traversal and correctly marks leaf boundaries.
dfs(node.left)Recursively serialize the left subtree.
Preorder traversal requires processing the left subtree immediately after the root to maintain correct order.
dfs(node.right)Recursively serialize the right subtree.
Completing preorder traversal by processing the right subtree ensures the entire tree is serialized.
return ",".join(res)Join the serialized list into a comma-separated string and return it.
Converting the list to a string produces the final serialized representation suitable for storage or transmission.
vals = data.split(',')Split the serialized string into tokens by commas.
Tokenizing the string prepares it for sequential recursive consumption during deserialization.
return NoneReturn None to represent a null node in the tree.
Returning None correctly reconstructs the absence of a node in the deserialized tree.
node.left = dfs()Recursively deserialize the left subtree.
Rebuilding the left subtree immediately after the root maintains preorder reconstruction order.
node.right = dfs()Recursively deserialize the right subtree.
Completing the right subtree reconstruction ensures the entire tree is rebuilt.
return nodeReturn the reconstructed node to the caller.
Returning the node links it into the reconstructed tree structure.
def serialize(self, root):Define the serialize method that returns the encoded tree string.
This method is the public entry point for turning the tree into a linear representation, so its signature defines the serialization contract.
def dfs(node):Define the recursive DFS helper function for serialization.
Encapsulating the preorder traversal logic in a helper function enables clean recursion and state management.
dfs(root)Start serialization by calling DFS on the root node.
Initiating the recursive traversal from the root triggers the full preorder serialization process.
def deserialize(self, data):Define the deserialize method that rebuilds the tree from the encoded string.
This method is the public entry point for reconstructing the tree from the encoded representation, so its signature defines the deserialization contract.
def dfs():Define the recursive DFS helper function for deserialization.
Encapsulating deserialization logic in a helper function enables clean recursive reconstruction of the tree.
return dfs()Start deserialization by calling DFS on the token list.
Initiating the recursive reconstruction from the first token triggers the full deserialization process.
Test Your Understanding
Why is it necessary to include explicit null markers during serialization?
Without null markers, the serialized string loses information about the tree's shape, making it impossible to reconstruct the original structure unambiguously during deserialization.
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