HardStringTreeDepth-First SearchBreadth-First SearchUpdated Sep 2026

428. Serialize and Deserialize N-ary Tree

Asked at Apple, TikTok

Difficulty

Hard

Time

O(n)

Space

O(n)

Pattern

String

Companies

2

Problem

Design two functions for an N-ary tree (a rooted tree where each node can have any number of children). serialize(root) turns the tree into a single string. deserialize(data) takes that string and rebuilds the exact same tree.

The format of the string is up to you. The only hard rule is round-trip correctness: deserialize(serialize(root)) must give back a tree with the same shape and the same values. The empty tree must also survive the round trip.

A clean way to do this is a pre-order DFS. For each node, write its value, then write how many children it has, then recurse into the children in order. For a missing node, write a special marker such as #. Because the child count is stored right next to the value, the decoder always knows exactly how many subtrees to read next — no guessing, no ambiguity. Your functions must be stateless: do not keep data in class members, globals or static variables between calls.

One tree, one string, and back again

432 children513 children62Root 1 has children 3, 2, 4; node 3 has children 5 and 6.serialize(root) → stringstore or send the stringdeserialize(string) → same treeThe string is the only thing that travels; the tree must berecoverable from it alone.
serialize turns the tree into text; deserialize must rebuild the exact same tree from that text.

Constraints

  • ●The number of nodes in the tree is in the range [0, 10^4].
  • ●0 <= Node.val <= 10^4
  • ●The height of the n-ary tree is less than or equal to 1000.
  • ●Do not use class member, global or static variables to store state; serialize and deserialize must be stateless.

Examples

Example 1
Inputroot = [1,null,3,2,4,null,5,6]
Output[1,null,3,2,4,null,5,6]
WhyThe tree has root 1 with children 3, 2, 4; node 3 has children 5 and 6. After serialize then deserialize, the rebuilt tree has the same values in the same positions, so the level-order printout matches the input.
Example 2
Inputroot = [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]
WhyThis is a deeper tree with many branches. The round trip still returns an identical tree, which shows the encoding handles variable child counts at every level.
Example 3
Inputroot = []
Output[]
WhyAn empty tree serializes to a marker for null, and deserializing that marker returns null, so the output is the empty tree again.

Asked At

2 companies
CompanyDifficulty
AppleHardView all Apple questions →
TikTokHardView all TikTok questions →

How to Think About It

1

Brute force: Use BFS with a delimiter to separate node values and track null markers for missing children at each level.

2

Improved: Use DFS with a special marker like "#" to represent null nodes and a count of children before each node value.

3

Better: Encode each node as "value,count" and recursively serialize children, using "#" for null subtrees.

4

Refined: Pre-order DFS traversal where you write the node value, then the number of children, then recurse into each child.

5

Optimal: Pre-order DFS with "value count" format separated by spaces. Write node count before children to handle variable branching without ambiguity.

Optimal Approach

The optimal approach uses a pre-order DFS traversal. For each node, write its value followed by the number of children, then recursively process each child. For null nodes, write "#" as a marker. During deserialization, read tokens one by one: if the token is "#", return null. Otherwise, parse the value and child count, create the node, then recursively deserialize each child. This produces an unambiguous encoding because the child count tells the deserializer exactly how many subtrees to expect. Both operations run in O(n) time and use O(n) space for the output string and recursion stack.

Pre-order DFS: value, child count, then children

4351visit 1 first62Pre-order starts at the root, then walks each child subtree from left to right.tokensval, count13325060204001234567891011Each node writes its value then its child count; leaves write count 0.read value, read countmake noderecurse count timesThe decoder reads a value and a count, then recursively builds exactly thatmany children.serialize: value, count, then childrennull → "#"deserialize: read value, read count, recurse
Writing the child count right after each value removes all ambiguity for the decoder.
ComplexityTime O(n)Space O(n)Every node is written once and read once; the O(n) space comes from the output string plus the recursion stack, which can be as deep as the tree height.

Solution Code

O(n) time
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children or []

class Codec:
    def serialize(self, root):
        parts = []
        def dfs(node):
            if not node:
                parts.append("#")
                return
            parts.append(str(node.val))
            parts.append(str(len(node.children)))
            for child in node.children:
                dfs(child)
        dfs(root)
        return " ".join(parts)

    def deserialize(self, data):
        tokens = iter(data.split())
        def dfs():
            token = next(tokens)
            if token == "#":
                return None
            val = int(token)
            count = int(next(tokens))
            node = Node(val)
            node.children = [dfs() for _ in range(count)]
            return node
        return dfs()

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Serialize and Deserialize N-ary Tree problem?

Design an algorithm to serialize and deserialize an N-ary tree to a string and back. Unlike binary trees, each node can have zero or more children, requiring a different encoding strategy to capture the variable branching structure.

How do you solve Serialize and Deserialize N-ary Tree?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Serialize and Deserialize N-ary Tree?

Serialize and Deserialize N-ary Tree is asked at Apple, TikTok. It is a hard difficulty problem.