Leetcode 428. Serialize and Deserialize N-ary Tree

Problem

You are tasked with implementing two functions that work together to save and restore a tree data structure where each node can have any number of children (not just two like a binary tree).

Your goal is to create a Codec class with:

• A serialize method that converts a multi-way tree into a compact string representation
• A deserialize method that takes that string and reconstructs the exact original tree structure

The tree is represented using a Node class where each node contains:

• An integer value (val)
• A list of child nodes (children)

Your encoding format must preserve:

• All node values
• The exact number of children each node has
• The order of children
• The complete tree structure

Requirements

1. Implement the serialize method to convert any tree (including null/empty trees) into a string
2. Implement the deserialize method to reconstruct the original tree from the serialized string
3. The deserialized tree must be structurally identical to the original
4. Your solution should handle edge cases like empty trees, single nodes, and deeply nested structures
5. Choose an encoding scheme that unambiguously represents the tree structure

Constraints

• Node values are integers in the range [-1000, 1000]
• The tree can have up to 10,000 nodes
• Each node can have 0 to 100 children
• Tree depth can be up to 1000 levels
• Your serialized string should be reasonably compact
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(n) for both operations

Examples

Example 1:

` Input tree: 1 /
3 2

serialize(root) → "1:2,3:0,2:0" deserialize("1:2,3:0,2:0") → reconstructed tree identical to input `

Example 2:

` Input tree: 1 / |
3 2 4 /
5 6

serialize(root) → "1:3,3:2,5:0,6:0,2:0,4:0" deserialize("1:3,3:2,5:0,6:0,2:0,4:0") → reconstructed tree identical to input `

Example 3:

` Input tree: null

serialize(null) → "" deserialize("") → null `

Hint 1: Choosing an Encoding Format Consider encoding each node with two pieces of information: its value and how many children it has. This allows you to know exactly how many child subtrees to expect when deserializing. For example, "5:3" could mean "node with value 5 has 3 children".

Hint 2: Traversal Strategy A depth-first traversal works well for both serialization and deserialization. When serializing, recursively encode each node and its children. When deserializing, recursively read a node's value and child count, then recursively deserialize exactly that many children.

Hint 3: Delimiter Selection Choose delimiters carefully to separate different parts of your encoding. For instance, use one delimiter (like ':') between a node's value and its child count, and another (like ',') between different nodes. Make sure your delimiters don't conflict with possible node values.

Full Solution `` Approach Explanation:

The solution uses a preorder depth-first traversal strategy with an explicit encoding scheme:

1. Serialization:

   • Handle the null/empty case by returning an empty string
   • For each node, encode it as "value:child_count" (e.g., "5:3" means value 5 with 3 children)
   • Use DFS to recursively visit and encode each node and all its children
   • Join all encoded nodes with commas to create the final string

2. Deserialization:

   • Split the string by commas to get individual node encodings
   • Use an index to track position in the token array
   • For each token, parse the value and child count
   • Create a new node and recursively deserialize exactly that many children
   • The recursive structure naturally reconstructs the tree hierarchy

Why This Works:

• By storing the child count with each node, we know exactly how many recursive calls to make during deserialization
• Preorder traversal ensures we process parents before children, making reconstruction straightforward
• The encoding is unambiguous: each token clearly specifies both the node's data and its structure

Complexity Analysis:

• Time Complexity: O(n) for both serialize and deserialize, where n is the number of nodes. We visit each node exactly once.
• Space Complexity: O(n) for the serialized string and O(h) for the recursion stack where h is the tree height (worst case O(n) for a skewed tree).

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:
        """
        Encodes a tree to a single string using preorder DFS traversal.
        Format: each node is encoded as "value:child_count"
        Nodes are separated by commas.
        """
        if not root:
            return ""
        
        result = []
        
        def dfs(node):
            if not node:
                return
            
            # Encode current node: value and number of children
            result.append(f"\{node.val\}:\{len(node.children)\}")
            
            # Recursively serialize all children
            for child in node.children:
                dfs(child)
        
        dfs(root)
        return ",".join(result)
    
    def deserialize(self, data: str) -> 'Node':
        """
        Decodes the encoded string back to a tree.
        Uses an iterator to consume tokens in preorder.
        """
        if not data:
            return None
        
        tokens = data.split(",")
        self.index = 0
        
        def build_tree():
            if self.index >= len(tokens):
                return None
            
            # Parse current token: "value:child_count"
            parts = tokens[self.index].split(":")
            val = int(parts[0])
            child_count = int(parts[1])
            self.index += 1
            
            # Create node
            node = Node(val, [])
            
            # Recursively build all children
            for _ in range(child_count):
                child = build_tree()
                if child:
                    node.children.append(child)
            
            return node
        
        return build_tree()