Serialize and Deserialize N-ary Tree
Hard · Graphs · Explanation and code example
Level order traversal
How it works
We can serialize the tree level by level using BFS. We use two sentinel markers: '#' to indicate the end of a level, and '$' to indicate switching to a different parent's children on the same level. During deserialization, we track nodes at the current and previous levels, using the sentinels to know when to move to the next level or switch parents.
Steps
Serialization:
- Use a queue initialized with the root and a level-end marker.
- For each node, append its value and enqueue all its children.
- After processing a node (if not the last on its level), add a child-switch marker.
- When encountering the level-end marker, append '#' and add a new level-end marker if the queue is not empty.
- Return the concatenated string.
Deserialization:
- Create the root node from the first character.
- Maintain current and previous level lists.
- Process each character:
- '#': Move to the next level by swapping lists and getting the next parent.
- '$': Switch to the next parent on the same level.
- Otherwise: Create a child node and attach it to the current parent.
- Return the root node.
Complexity
-
Time complexity:
-
Serialization:O(N). For every node, we add 2 different values to the final string and every node is processed exactly once. We add the value of the node itself and we also add the child switch sentinel. Also, for the nodes that end a particular level, we add the level end sentinel. -
Deserialization:O(N). For deserialization, we process the entire string, one character at a time and also construct the tree along the way. So, the overall time complexity for deserialization is2N = O(N).
-
-
Space complexity:
-
Serialization:O(N). The space occupied by the serialization helper function is through the queue and the final string that is produced. We know the size of the final string to be2N. So that is one part of the space complexity. The other part is the one occupied by the queue which isO(N). Overall, the space isO(N). -
Deserialization:O(N). For deserialization, the space is mostly occupied by the two lists that we use. The space complexity there isO(N). Note that when we re-initialize a list, the memory that was allocated earlier is deallocated by the garbage collector and it's essentially equal to a single list of sizeO(N).
-
Where
Nis the number of nodes in the tree.
Things to watch for
Losing Children Count Information
Unlike binary trees where each node has exactly two children slots, n-ary trees have variable numbers of children. Failing to encode how many children each node has makes it impossible to correctly reconstruct the tree during deserialization. Each serialization approach must capture this information somehow (explicit count, sentinels, or parent references).
Incorrect Character Encoding for Values
When converting node values to single characters using ASCII offsets (like chr(val + 48)), values outside the valid range cause issues. This approach only works for small, non-negative integers. Larger values or negative numbers require a different encoding strategy with proper delimiters.
Mishandling the Children List Initialization
When creating nodes during deserialization, forgetting to initialize the children list (or initializing it as null instead of an empty list) causes null pointer exceptions when adding children later. Always initialize the children collection before attempting to add child nodes.
Confusing Parent-Child Relationship Direction
In the parent-child ID approach, mixing up which ID refers to the parent versus the child node leads to a completely incorrect tree structure. The serialized data must clearly distinguish between a node's own identity and its parent's identity.
Off-by-One Errors in Sentinel-Based Approaches
When using sentinels to mark the end of children (like #), forgetting to increment the index after consuming the sentinel causes the deserializer to get stuck or skip actual node values. The index must advance both when creating nodes and when encountering sentinels.
Python code example
import collections
class Codec:
def _serializeHelper(self, root, serializedList):
queue = collections.deque()
queue.append(root)
queue.append(None)
while queue:
# Pop a node
node = queue.popleft()
# If this is an "endNode", we need to add another one
# to mark the end of the current level unless this
# was the last level.
if (node == None):
# We add a sentinal value of "#" here
serializedList.append("#")
if queue:
queue.append(None)
elif node == "C":
# Add a sentinal value of "$" here to mark the switch to a
# different parent.
serializedList.append("$")
else:
# Add value of the current node and add all of it's
# children nodes to the queue. Note how we convert
# the integers to their corresponding ASCII counterparts.
serializedList.append(chr(node.val + 48))
for child in node.children:
queue.append(child)
# If this not is NOT the last one on the current level,
# add a childNode as well since we move on to processing
# the next node.
if queue[0] != None:
queue.append("C")
def serialize(self, root: 'Node') -> str:
if not root:
return ""
serializedList = []
self._serializeHelper(root, serializedList)
return "".join(serializedList)
def _deserializeHelper(self, data, rootNode):
# We move one level at a time and at every level, we need access
# to the nodes on the previous level as well so that we can form
# the children arrays properly. Hence two arrays.
prevLevel, currentLevel = collections.deque(), collections.deque()
currentLevel.append(rootNode)
parentNode = rootNode
# Process the characters in the string one at a time.
for i in range (1, len(data)):
if data[i] == "#":
# Special processing for end of level. We need to swap the
# array lists. Here, we simply re-initialize the "currentLevel"
# arraylist rather than clearing it.
prevLevel = currentLevel
currentLevel = collections.deque()
# Since we move one level down, we take the parent as the first
# node on the current level.
parentNode = prevLevel.popleft() if prevLevel else None
else:
if data[i] == "$":
# Special handling for change in parent on the same level
parentNode = prevLevel.popleft() if prevLevel else None
else:
childNode = Node(ord(data[i]) - 48, [])
currentLevel.append(childNode)
parentNode.children.append(childNode)
def deserialize(self, data: str) -> 'Node':
if not data:
return None
rootNode = Node(ord(data[0]) - 48, [])
self._deserializeHelper(data, rootNode)
return rootNode
C++ code example
class Codec {
private:
void _serializeHelper(Node* root, string& serializedList) {
deque<variant<Node*, char>> queue;
queue.push_back(root);
queue.push_back(nullptr);
while (!queue.empty()) {
// Pop a node
auto front = queue.front();
queue.pop_front();
// If this is an "endNode", we need to add another one
// to mark the end of the current level unless this
// was the last level.
if (holds_alternative<Node*>(front) && get<Node*>(front) == nullptr) {
// We add a sentinel value of "#" here
serializedList += "#,";
if (!queue.empty()) {
queue.push_back(nullptr);
}
}
// Add a sentinel value of "$" here to mark the switch to a
// different parent.
else if (holds_alternative<char>(front) && get<char>(front) == 'C') {
serializedList += "$,";
}
else {
// Add value of the current node and add all of its
// children nodes to the queue.
Node* node = get<Node*>(front);
serializedList += to_string(node->val) + ",";
for (Node* child : node->children) {
queue.push_back(child);
}
// If this node is NOT the last one on the current level,
// add a childNode as well since we move on to processing
// the next node.
if (!queue.empty() &&
!(holds_alternative<Node*>(queue.front()) && get<Node*>(queue.front()) == nullptr)) {
queue.push_back('C');
}
}
}
}
void _deserializeHelper(const string& data, Node* rootNode) {
// We move one level at a time and at every level, we need access
// to the nodes on the previous level as well so that we can form
// the children arrays properly. Hence two arrays.
deque<Node*> prevLevel, currentLevel;
currentLevel.push_back(rootNode);
Node* parentNode = rootNode;
int i = 0;
// Skip past first value (already parsed for rootNode)
while (i < data.length() && data[i] != ',') i++;
i++; // skip comma
// Process the characters in the string one at a time.
while (i < data.length()) {
// Special processing for end of level. We need to swap the
// array lists. Here, we simply re-initialize the "currentLevel"
// arraylist rather than clearing it.
if (data[i] == '#') {
prevLevel = currentLevel;
currentLevel = deque<Node*>();
// Since we move one level down, we take the parent as the first
// node on the current level.
if (!prevLevel.empty()) {
parentNode = prevLevel.front();
prevLevel.pop_front();
} else {
parentNode = nullptr;
}
i += 2; // skip "#,"
}
// Special handling for change in parent on the same level
else if (data[i] == '$') {
if (!prevLevel.empty()) {
parentNode = prevLevel.front();
prevLevel.pop_front();
} else {
parentNode = nullptr;
}
i += 2; // skip "$,"
}
else {
// Parse number (handles multi-digit values)
int val = 0;
while (i < data.length() && data[i] != ',') {
val = val * 10 + (data[i] - '0');
i++;
}
i++; // skip comma
Node* childNode = new Node(val, vector<Node*>());
currentLevel.push_back(childNode);
parentNode->children.push_back(childNode);
}
}
}
public:
string serialize(Node* root) {
if (root == nullptr) {
return "";
}
string serializedList;
_serializeHelper(root, serializedList);
return serializedList;
}
Node* deserialize(string data) {
if (data.empty()) {
return nullptr;
}
// Parse first value (handles multi-digit values)
int val = 0;
int i = 0;
while (i < data.length() && data[i] != ',') {
val = val * 10 + (data[i] - '0');
i++;
}
Node* rootNode = new Node(val, vector<Node*>());
_deserializeHelper(data, rootNode);
return rootNode;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.