Solutions

1. Parent Child relationships

Intuition

One way to serialize an n-ary tree is to record each node along with a unique identifier and its parent's identifier. During serialization, we assign each node an ID, store its value, and record its parent's ID. During deserialization, we first create all nodes, then link children to their parents using the stored parent IDs. This approach explicitly encodes the tree structure through parent references.

Algorithm

Serialization:

Traverse the tree using DFS, assigning each node a unique identity starting from 1.
For each node, append three values: its identity, its value, and its parent's identity (or 'N' for the root).
Return the concatenated string.

Deserialization:

Parse the string in chunks of 3 characters to extract identity, value, and parent ID.
Create all nodes and store them in a map keyed by identity.
For each non-root node, find its parent using the parent ID and add the node to the parent's children list.
Return the root node.

class WrappableInt:
        def __init__(self, x):
            self.value = x
        def getValue(self):
            return self.value
        def increment(self):
            self.value += 1

class Codec:

    def serialize(self, root: 'Node') -> str:
        serializedList = []
        self._serializeHelper(root, serializedList, WrappableInt(1), None)
        return "".join(serializedList)

    def _serializeHelper(self, root, serializedList, identity, parentId):
        if not root:
            return

        # Own identity
        serializedList.append(chr(identity.getValue() + 48))

        # Actual value
        serializedList.append(chr(root.val + 48))

        # Parent's identity
        serializedList.append(chr(parentId + 48) if parentId else 'N')

        parentId = identity.getValue()
        for child in root.children:
            identity.increment()
            self._serializeHelper(child, serializedList, identity, parentId)

    def deserialize(self, data: str) -> 'Node':
        if not data:
            return None

        return self._deserializeHelper(data)

    def _deserializeHelper(self, data):

        nodesAndParents = {}
        for i in range(0, len(data), 3):
            identity = ord(data[i]) - 48
            orgValue = ord(data[i + 1]) - 48
            parentId = ord(data[i + 2]) - 48
            nodesAndParents[identity] = (parentId, Node(orgValue, []))

        for i in range(3, len(data), 3):

            # Current node
            identity = ord(data[i]) - 48
            node = nodesAndParents[identity][1]

            # Parent node
            parentId = ord(data[i + 2]) - 48
            parentNode = nodesAndParents[parentId][1]

            # Attach!
            parentNode.children.append(node)

        return nodesAndParents[ord(data[0]) - 48][1]

Time & Space Complexity

Time complexity:
- Serialization : $O(N)$ . For every node, we add 3 different values to the final string and every node is processed exactly once.
- Deserialization : $O(N)$ . Technically, it is $3N$ for the first for loop and $N$ for the second one. However, constants are ignored in asymptotic complexity analysis. So, the overall time complexity for deserialization is $O(N)$ .
Space complexity:
- Serialization : $O(N)$ . The space occupied by the serialization helper function is through recursion stack and the final string that is produced. Usually, we don't take into consideration the space of the output. However, in this case, the output is something which is not fixed. For all we know, someone might be able to generate a string of size $N/2$ . We don't know! So, the size of the final string is a part of the space complexity here. Overall, the space is $4N = O(N)$ .
- Deserialization : $O(N)$ . The space occupied by the deserialization helper function is through the hash map. For each entry, we have 3 values. Thus, we can say the space is $3N$ . But again, the constants don't really matter in asymptotic complexity. So, the overall space is $O(N)$ .

Where $N$ is the number of nodes in the tree.

2. Depth First Search with Children Sizes

Intuition

Instead of storing parent IDs, we can store each node's value followed by its number of children. This gives us enough information to reconstruct the tree during DFS deserialization. When we encounter a node, we know exactly how many children to expect, so we can recursively build each subtree. This approach is more space-efficient since we only need 2 characters per node.

Algorithm

Serialization:

For each node, append its value followed by the count of its children.
Recursively serialize each child.
Return the concatenated string.

Deserialization:

Maintain an index pointer into the string.
Read the value at the current index and create a node.
Read the next character to get the number of children.
Recursively deserialize that many child nodes.
Return the constructed node.

class WrappableInt:
        def __init__(self, x):
            self.value = x
        def getValue(self):
            return self.value
        def increment(self):
            self.value += 1

class Codec:
    
    def serialize(self, root: 'Node') -> str:
        serializedList = []
        self._serializeHelper(root, serializedList)

        return "".join(serializedList)
    
    def _serializeHelper(self, root, serializedList):
        if not root:
            return
        
        # Actual value
        serializedList.append(chr(root.val + 48))
        
        # Number of children
        serializedList.append(chr(len(root.children) + 48))
        
        for child in root.children:
            self._serializeHelper(child, serializedList)
    
    def deserialize(self, data: str) -> 'Node':
        if not data:
            return None
        
        return self._deserializeHelper(data, WrappableInt(0))
        
    def _deserializeHelper(self, data, index):
        
        if index.getValue() == len(data):
            return None
        
        # The invariant here is that the "index" always
        # points to a node and the value next to it 
        # represents the number of children it has.
        node = Node(ord(data[index.getValue()]) - 48, [])
        index.increment()
        numChildren = ord(data[index.getValue()]) - 48
        for _ in range(numChildren):
            index.increment()
            node.children.append(self._deserializeHelper(data, index))

        return node

Time & Space 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.
- 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 is $2N = O(N)$ .
Space complexity:
- Serialization : $O(N)$ . The space occupied by the serialization helper function is through recursion stack and the final string that is produced. We know the size of the final string to be $2N$ . So, that is one part of the space complexity. The other part is the one occupied by the recursion stack which is $O(N)$ . Overall, the space is $O(N)$ .
- Deserialization : $O(N)$ . For deserialization, the space occupied is by the recursion stack only. We don't use any other intermediate data structures like we did in the previous approach and simply rely on the information in the string and recursion to work it's magic. So, the space complexity would be $O(N)$ since this is not a balanced tree of any sort. It's not even binary.

Where $N$ is the number of nodes in the tree.

3. Depth First Search with a Sentinel

Intuition

Another approach uses a sentinel character (like '#') to mark the end of a node's children. After serializing a node's value and all its children recursively, we append the sentinel. During deserialization, we read nodes and recursively build children until we hit the sentinel, which signals that all children for the current node have been processed.

Algorithm

Serialization:

For each node, append its value.
Recursively serialize each child.
Append the sentinel '#' to mark the end of this node's subtree.
Return the concatenated string.

Deserialization:

Maintain an index pointer into the string.
Read the value at the current index and create a node.
Increment the index and repeatedly deserialize children until the sentinel '#' is encountered.
Skip the sentinel and return the constructed node.

class WrappableInt:
        def __init__(self, x):
            self.value = x
        def getValue(self):
            return self.value
        def increment(self):
            self.value += 1

class Codec:
    
    def serialize(self, root: 'Node') -> str:
        serializedList = []
        self._serializeHelper(root, serializedList)
        return "".join(serializedList)
    
    def _serializeHelper(self, root, serializedList):
        if not root:
            return
        
        # Actual value
        serializedList.append(chr(root.val + 48))
        
        for child in root.children:
            self._serializeHelper(child, serializedList)
            
        # Add the sentinel to indicate that all the children
        # for the current node have been processed 
        serializedList.append('#')    
    
    def deserialize(self, data: str) -> 'Node':
        if not data:
            return None
        
        return self._deserializeHelper(data, WrappableInt(0))
        
    def _deserializeHelper(self, data, index):
        
        if index.getValue() == len(data):
            return None
        
        node = Node(ord(data[index.getValue()]) - 48, [])
        index.increment()
        while (data[index.getValue()] != '#'):
            node.children.append(self._deserializeHelper(data, index))
        
        
        # Discard the sentinel. Note that this also moves us
        # forward in the input string. So, we don't have the index
        # progressing inside the above while loop!
        index.increment()
        return node

Time & Space 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.
- 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 is $2N = O(N)$ .
Space complexity:
- Serialization : $O(N)$ . The space occupied by the serialization helper function is through recursion stack and the final string that is produced. We know the size of the final string to be $2N$ . So, that is one part of the space complexity. The other part is the one occupied by the recursion stack which is $O(N)$ . Overall, the space is $O(N)$ .
- Deserialization : $O(N)$ . For deserialization, the space occupied is by the recursion stack only. We don't use any other intermediate data structures like we did in the previous approach and simply rely on the information in the string and recursion to work it's magic. So, the overall space complexity would be $O(N)$ .

Where $N$ is the number of nodes in the tree.

4. Level order traversal

Intuition

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.

Algorithm

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.

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

Time & Space 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 is $2N = 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 be $2N$ . So that is one part of the space complexity. The other part is the one occupied by the queue which is $O(N)$ . Overall, the space is $O(N)$ .
- Deserialization : $O(N)$ . For deserialization, the space is mostly occupied by the two lists that we use. The space complexity there is $O(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 size $O(N)$ .

Where $N$ is the number of nodes in the tree.

Common Pitfalls

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.