LeetCode 428: Serialize and Deserialize N-ary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 428: Serialize and Deserialize N-ary Tree?

In LeetCode 428: Serialize and Deserialize N-ary Tree, you’re given an N-ary tree where each Node has a value and a list of children (e.g., root 1 with children [2, 3, 4]), and you need to:

• Serialize: Convert the tree into a string (e.g., "1,3,2,3,5,6,4").
• Deserialize: Rebuild the tree from that string.

The tree isn’t binary—nodes can have any number of kids—so the solution must track child counts or structure explicitly. For example, serializing 1 → [2, 3 → [5, 6], 4] might yield "1,3,2,3,5,6,4", where "3" after 1 indicates three children, followed by their values and subtrees. You implement both methods in a Codec class, handling any valid N-ary tree.

Problem Statement

• Input:
• Serialize: root (N-ary tree Node).
• Deserialize: data (string).
• Output:
• Serialize: A string representing the tree.
• Deserialize: The Node root of the reconstructed tree.
• Rules:
• N-ary tree: Each node has a value and a list of children.
• Serialize/deserialize must be reversible (string → tree → string matches).
• In-place or minimal extra nodes preferred.

Constraints

• Number of nodes is in range [0, 10⁴].
• 0 <= Node.val <= 10⁴.
• Values are unique.
• Children list length ≤ 10⁴.

Examples

• Input: [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]
• Serialized: "1,5,2,0,3,2,6,7,4,1,8,5,2,9,10,11,1,12,13,1,14".
• Deserialized: Rebuilds original tree.
• Input: [1,null,3,null,5,6]
• Serialized: "1,1,3,2,5,6".
• Input: []
• Serialized: "".

Understanding the Problem: Packing and Unpacking the Tree

To solve LeetCode 428: Serialize and Deserialize N-ary Tree in Python, we need to encode an N-ary tree into a string and decode it back, preserving its structure. A naive idea might be to just list values—but without child counts or separators, we’d lose the tree shape! Instead, we’ll use:

• Best Solution (Preorder Traversal with Child Count): O(n) time, O(n) space—encodes efficiently.
• Alternative Solution (Level-Order Traversal with Separators): O(n) time, O(n) space—uses breadth-first order.

Let’s dive into the preorder solution with a clear, step-by-step explanation.

Best Solution: Preorder Traversal with Child Count

Why This Is the Best Solution

The preorder traversal with child count method is the top pick because it’s efficient—O(n) time for both serialize and deserialize, O(n) space (recursion or queue)—and naturally captures the N-ary tree’s structure. It serializes by visiting each node in preorder (root, then children), appending the value and child count, and deserializes by reconstructing recursively with a pointer. It’s like packing the tree into a string with a roadmap and unpacking it by following the trail!

How It Works

Think of the tree as a family you’re listing:

• Serialize:
• Preorder: Root value, number of children, then children recursively.
• Join with commas (e.g., "1,3,2,0,3,2,5,6,4").
• Deserialize:
• Split string into list (e.g., ["1", "3", "2", "0", ...]).
• Use pointer to track position, build tree recursively:
• Take value, child count, recurse for each child.
• Why This Works:
• Preorder ensures parent-child order.
• Child count disambiguates N-ary structure.
• It’s like writing a family tree list and rebuilding it step-by-step!

Step-by-Step Example

Example: [1,null,2,3,4]

• Tree:

1 /|\ 2 3 4

• Serialize:
• 1, 3 kids: "1,3".
• 2, 0 kids: "2,0".
• 3, 0 kids: "3,0".
• 4, 0 kids: "4,0".
• Result: "1,3,2,0,3,0,4,0".
• Deserialize:
• List: ["1", "3", "2", "0", "3", "0", "4", "0"].
• Pointer = 0:
• Root = 1, kids = 3, move to 2.
• Child 1: 2, kids = 0, move to 4.
• Child 2: 3, kids = 0, move to 6.
• Child 3: 4, kids = 0, move to 8.
• Result: Root 1 with children [2, 3, 4].

Example: [1,null,3,null,5,6]

• Serialize: "1,1,3,2,5,6".
• Deserialize:
• List: ["1", "1", "3", "2", "5", "6"].
• Root = 1, 1 kid: 3, 2 kids: 5, 6.
• Result: 1 → [3 → [5, 6]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy code# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

class Codec:
    def serialize(self, root: 'Node') -> str:
        if not root:
            return ""

        # Step 1: Preorder traversal with child count
        result = []

        def preorder(node):
            if not node:
                return
            result.append(str(node.val))
            result.append(str(len(node.children)))
            for child in node.children:
                preorder(child)

        preorder(root)
        return ",".join(result)

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

        # Step 2: Split into list and deserialize
        values = data.split(",")
        self.index = 0

        def dfs():
            if self.index >= len(values):
                return None

            # Create node with value
            node = Node(int(values[self.index]))
            self.index += 1
            num_children = int(values[self.index])
            self.index += 1

            # Recursively add children
            for _ in range(num_children):
                child = dfs()
                node.children.append(child)

            return node

        return dfs()

• Line 2-6: Node class (given):
• val: Node value.
• children: List of child nodes.
• Serialize (Line 9-23):
• Line 11-12: Empty tree → "".
• Line 15-21: Preorder:
• Append val, child count.
• Recurse on each child.
• Line 22: Join with commas.
• Deserialize (Line 25-46):
• Line 27-28: Empty string → None.
• Line 31-32: Split string, init pointer.
• Line 35-45: DFS:
• Line 38-40: Create node, get child count, advance index.
• Line 43-44: Recurse for each child, append to list.
• Line 47: Start DFS from root.
• Time Complexity: O(n)—each node processed once.
• Space Complexity: O(n)—string or recursion stack.

This is like packing a family tree into a string and unpacking it with a roadmap!

Alternative Solution: Level-Order Traversal with Separators

Why an Alternative Approach?

The level-order traversal with separators method serializes the tree breadth-first, using separators (e.g., "#") to mark level ends, and deserializes by reconstructing level-by-level with a queue. It’s O(n) time and O(n) space—more intuitive for some but slightly more complex. It’s like listing the family tree floor-by-floor and rebuilding it layer-by-layer!

How It Works

Picture it as layering the tree:

• Serialize:
• BFS with queue, append value, child count, "#" per level.
• (e.g., "1,3,2,0,3,0,4,0,#").
• Deserialize:
• Split by "#", process each level with queue.

Step-by-Step Example

Example: [1,null,2,3,4]

• Serialize:
• Level 1: "1,3".
• Level 2: "2,0,3,0,4,0".
• Result: "1,3,2,0,3,0,4,0,#".
• Deserialize:
• Levels: ["1,3", "2,0,3,0,4,0"].
• Root 1, 3 kids: Queue [2, 3, 4].
• Result: 1 → [2, 3, 4].

Code for Level-Order Approach (Simplified)

Copy codeclass Codec:
    def serialize(self, root: 'Node') -> str:
        if not root:
            return ""

        result = []
        queue = [root]
        while queue:
            level = []
            next_level = []
            for node in queue:
                result.append(str(node.val))
                result.append(str(len(node.children)))
                next_level.extend(node.children)
            result.append("#")
            queue = next_level
        return ",".join(result)

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

        levels = data.split("#")[:-1]  # Skip last empty
        values = levels[0].split(",")
        root = Node(int(values[0]))
        queue = [(root, int(values[1]))]
        level_idx = 1

        while queue and level_idx < len(levels):
            next_queue = []
            level_vals = levels[level_idx].split(",")
            val_idx = 0
            for parent, num_kids in queue:
                for _ in range(num_kids):
                    child = Node(int(level_vals[val_idx]))
                    parent.children.append(child)
                    next_queue.append((child, int(level_vals[val_idx + 1])))
                    val_idx += 2
            queue = next_queue
            level_idx += 1

        return root

• Time Complexity: O(n)—each node processed once.
• Space Complexity: O(n)—queue and string.

It’s a layer-by-layer packer!

Comparing the Two Solutions

• Preorder with Child Count (Best):
• Pros: O(n), O(n), simple and direct.
• Cons: Recursive depth.
• Level-Order with Separators (Alternative):
• Pros: O(n), O(n), level clarity.
• Cons: More complex deserialize.

Preorder wins for simplicity.

Additional Examples and Edge Cases

• []: "".
• [1]: "1,0".
• [1,null,2]: "1,1,2,0".

Preorder handles all.

Complexity Breakdown

• Preorder: Time O(n), Space O(n).
• Level-Order: Time O(n), Space O(n).

Preorder’s sleek.

Key Takeaways

• Preorder: Pack with counts!
• Level-Order: Layer it up!
• N-ary: Kids complicate.
• Python Tip: Lists rock—see [Python Basics](/python/basics).

Final Thoughts: Serialize That Tree

LeetCode 428: Serialize and Deserialize N-ary Tree in Python is a tree-packing quest. Preorder with child count zips it fast, while level-order layers it clear. Want more tree fun? Try LeetCode 297: Serialize and Deserialize Binary Tree or LeetCode 589: N-ary Tree Preorder Traversal. Ready to pack? Head to Solve LeetCode 428 on LeetCode and serialize that tree today!