Serialize and Deserialize N-ary Tree

Serialize and Deserialize an N-ary Tree asks you to turn a tree into a flat string and back again, with no loss. Unlike a binary tree, each node can have any number of children, so the trick is recording how many children follow each value.

The slow way first

A tempting idea is to store the tree with brackets, like 1[3[5][6]][2][4], then parse the brackets back. That works, but bracket parsing is fiddly: you must track nesting depth, match opening to closing brackets, and handle multi-digit values. It is easy to get an off-by-one wrong on a deeply nested tree.

The question to ask: what is the minimum I must record so the rebuild is unambiguous? If I know each node value and how many children it has, I never need brackets at all — the counts alone tell me where each subtree ends.

The idea: write value, then child count

Do a preorder DFS. When you visit a node, append two things: its value, then its number of children. Then recurse into each child in order. The child count is the key: during the rebuild, after reading a value and a count k, you know to read exactly k children next, recursively.

The whole scheme is symmetric: serialize writes value then count; deserialize reads value then count. No delimiters, no brackets, no ambiguity.

Walk through it

Step through the animation. The DFS lights up nodes in preorder: 1, then 3, then 3's children 5 and 6, then back up to 2 and 4. Each node appends its value and child count to the encoded string. A count of 0 marks a leaf. By the end the tree is the flat list 1 3 3 2 5 0 6 0 2 0 4 0. Deserialize then reads it left to right, recreating each node and pulling exactly its declared number of children.

Pseudocode

serialize(root):
    out = empty list
    dfs(node):
        append node.value to out
        append (number of node.children) to out
        for each child in node.children:
            dfs(child)
    dfs(root)
    return out
 
deserialize(tokens):
    read tokens left to right
    build():
        value = next token
        count = next token
        node = new Node(value)
        repeat count times: node.children.append(build())
        return node
    return build()

The Python solution

def serialize(root):
    out = []
    def dfs(node):
        out.append(node.val)
        out.append(len(node.children))
        for child in node.children:
            dfs(child)
    dfs(root)
    return out
 
def deserialize(tokens):
    it = iter(tokens)
    def build():
        node = Node(next(it))
        count = next(it)
        node.children = [build() for _ in range(count)]
        return node
    return build()

• dfs appends the value, then len(node.children) — the count is what makes brackets unnecessary.
• The for loop recurses into each child in order, so the output is strictly preorder.
• In deserialize, it = iter(tokens) lets next(it) pull tokens one at a time across recursive calls.
• build reads a value, then a count, then calls itself exactly count times to fill node.children.
• Because both sides agree on the order — value, count, children — the reconstruction is exact.

Complexity

Both directions touch every node a constant number of times, so they are linear. The space is O(n) for the token list plus O(h) recursion stack, where h is the tree height.

When this pattern shows up

Practice