Serialize and Deserialize N-ary Tree - Solution & Explanation
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 an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, you may serialize the following 3-ary tree
as [1 [3[5 6] 2 4]]. Note that this is just an example, you do not necessarily need to follow this format.
Or you can follow LeetCode's level order traversal serialization format, where each group of children is separated by the null value.
For example, the above tree may be serialized as [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14].
You do not necessarily need to follow the above-suggested formats, there are many more different formats that work so please be creative and come up with different approaches yourself.
Example 1:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Example 2:
Input: root = [1,null,3,2,4,null,5,6] Output: [1,null,3,2,4,null,5,6]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. 0 <= Node.val <= 104- The height of the n-ary tree is less than or equal to
1000 - Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
Approach Overview
Problem Overview: You need to convert an N-ary tree into a string so it can be stored or transmitted, and then reconstruct the exact same tree from that string. The structure must remain identical: node values and parent‑child relationships must be preserved.
Approach 1: DFS Preorder Serialization with Child Count (O(n) time, O(n) space)
The common solution uses preorder traversal from Depth-First Search. For each node, store its value followed by the number of children. During serialization, recursively visit nodes and append value, childCount to a string or list. During deserialization, read tokens sequentially: create a node, then recursively build the next childCount children. The key insight is that the child count completely defines the tree structure, so the parser always knows how many recursive calls to make.
This approach processes each node exactly once, giving O(n) time complexity. The serialized output stores two tokens per node (value and child count), so the storage cost is also O(n). Recursive calls use up to O(h) stack space where h is the tree height.
Approach 2: BFS Level Order Serialization (O(n) time, O(n) space)
A second option uses Breadth-First Search with a queue. Serialize nodes level by level. For each node, record its value and the number of children, then enqueue all children. Deserialization mirrors this process: read the root first, push it into a queue, then reconstruct children for each node based on the stored child count.
This approach still visits each node once, so the runtime remains O(n). The queue may hold up to an entire level of nodes, leading to O(w) auxiliary space where w is the maximum width of the tree. The serialized string size remains linear in the number of nodes.
Both strategies rely on representing structure explicitly. Without storing the number of children (or equivalent delimiters), reconstructing the tree would be ambiguous. The serialized format is essentially a compact structural encoding of the tree.
Recommended for interviews: DFS preorder with child counts is the most common implementation. It produces a compact representation and maps naturally to recursive deserialization. Showing the BFS alternative demonstrates deeper understanding, but the DFS version is typically what interviewers expect because it is simpler to implement correctly.
Solution
We can serialize an N-ary tree with level order traversal. Start from the root, append its value, and enqueue it. Each time we dequeue a node, we append the values of all its children and enqueue them, then append a special character # to mark the end of that node's children. Finally we join the values with commas.
During deserialization, we split the string by the delimiter. Create the root from the first value and enqueue it. For each dequeued node, keep reading the following values as its children until we meet #.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the N-ary tree.
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Preorder with Child Count | O(n) | O(n) | Most common interview solution; simple recursive structure |
| BFS Level Order Serialization | O(n) | O(n) | Useful when you prefer iterative logic with queues |
| DFS with Delimiter Markers | O(n) | O(n) | Alternative format using sentinel markers instead of child counts |
Video Solution
[Java] Leetcode 428. Serialize and Deserialize N-ary Tree [N-ary Tree #1] • Eric Programming • 5,754 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Serialize and Deserialize N-ary Tree easy or hard?
Serialize and Deserialize N-ary Tree Python/Java solution
How to solve Serialize and Deserialize N-ary Tree in O(n)?
What is the best approach for Serialize and Deserialize N-ary Tree?
Is Serialize and Deserialize N-ary Tree asked at Google/Amazon/Meta?
What data structure is used in Serialize and Deserialize N-ary Tree?
What is the time complexity of Serialize and Deserialize N-ary Tree?
Ready to solve this problem?
Practice Serialize and Deserialize N-ary Tree with our built-in code editor and test cases.
Practice on FleetCode