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:
[0, 104].0 <= Node.val <= 1041000Problem 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.
Solutions for this problem are being prepared.
Try solving it yourself| 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 |
[Java] Leetcode 428. Serialize and Deserialize N-ary Tree [N-ary Tree #1] • Eric Programming • 5,704 views views
Watch 9 more video solutions →Practice Serialize and Deserialize N-ary Tree with our built-in code editor and test cases.
Practice on FleetCode