Serialize and Deserialize N-ary Tree
Asked at Apple
Problem
Design an algorithm to serialize and deserialize an N-ary tree to a string and back. Unlike binary trees, each node can have zero or more children, requiring a different encoding strategy to capture the variable branching structure.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Hard | View all Apple questions → |
How to Think About It
Brute force: Use BFS with a delimiter to separate node values and track null markers for missing children at each level.
Improved: Use DFS with a special marker like "#" to represent null nodes and a count of children before each node value.
Better: Encode each node as "value,count" and recursively serialize children, using "#" for null subtrees.
Refined: Pre-order DFS traversal where you write the node value, then the number of children, then recurse into each child.
Optimal: Pre-order DFS with "value count" format separated by spaces. Write node count before children to handle variable branching without ambiguity.
Optimal Approach
The optimal approach uses a pre-order DFS traversal. For each node, write its value followed by the number of children, then recursively process each child. For null nodes, write "#" as a marker. During deserialization, read tokens one by one: if the token is "#", return null. Otherwise, parse the value and child count, create the node, then recursively deserialize each child. This produces an unambiguous encoding because the child count tells the deserializer exactly how many subtrees to expect. Both operations run in O(n) time and use O(n) space for the output string and recursion stack.
Solution Code
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children or []
class Codec:
def serialize(self, root):
parts = []
def dfs(node):
if not node:
parts.append("#")
return
parts.append(str(node.val))
parts.append(str(len(node.children)))
for child in node.children:
dfs(child)
dfs(root)
return " ".join(parts)
def deserialize(self, data):
tokens = iter(data.split())
def dfs():
token = next(tokens)
if token == "#":
return None
val = int(token)
count = int(next(tokens))
node = Node(val)
node.children = [dfs() for _ in range(count)]
return node
return dfs()Frequently Asked Questions
What is the Serialize and Deserialize N-ary Tree problem?
Design an algorithm to serialize and deserialize an N-ary tree to a string and back. Unlike binary trees, each node can have zero or more children, requiring a different encoding strategy to capture the variable branching structure.
How do you solve Serialize and Deserialize N-ary Tree?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Serialize and Deserialize N-ary Tree?
Serialize and Deserialize N-ary Tree is asked at Apple. It is a hard difficulty problem.