LeetCode Solutions Blog

Encode N-ary Tree to Binary Tree

Number: 771

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Design an algorithm to encode an N-ary tree into a binary tree and decode the binary tree to recover the original N-ary tree. In an N-ary tree, each node can have up to N children while a binary tree node has at most two children. The challenge is to ensure that the encoding and decoding algorithms are stateless and one can correctly reconstruct the original tree structure.

Key Insights

Use the Left-Child Right-Sibling representation.
In the binary tree:
- The left pointer of a node will represent its first child.
- The right pointer links siblings (secondary children of the same parent).
Encoding involves converting each N-ary node by mapping its first child to the binary tree left pointer and chaining additional children via the right pointers.
Decoding reverses the process by traversing the left pointer for the first child and following right pointers for further siblings.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes (each node is processed once).
Space Complexity: O(N) due to recursion stack or auxiliary data structures used during traversal.

Solution

We employ the left-child right-sibling technique. For encoding:

Create a binary tree node corresponding to the N-ary node.
Set its left pointer to the encoding of the first child.
For the remaining children, link them via right pointers iteratively. For decoding:
Convert the binary tree node back to an N-ary node.
Traverse the left subtree (which encodes the list of children) by iterating over the chain of right pointers, decoding each and adding them as children of the N-ary node.

This method maintains a one-to-one mapping between the N-ary tree and its binary tree representation.

Code Solutions

# Definition for an N-ary tree node.
class NaryNode:
    def __init__(self, val, children=None):
        self.val = val
        self.children = children if children is not None else []

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    # Encodes an N-ary tree to a binary tree.
    def encode(self, root: 'NaryNode') -> 'TreeNode':
        if root is None:
            return None
        # Create corresponding binary tree node with the same value.
        binaryNode = TreeNode(root.val)
        if not root.children:
            return binaryNode
        
        # Use the left pointer of binaryNode to hold the encoding of its first child.
        binaryNode.left = self.encode(root.children[0])
        
        # Chain the rest of the children using right pointers.
        currentBinaryChild = binaryNode.left
        for child in root.children[1:]:
            currentBinaryChild.right = self.encode(child)
            currentBinaryChild = currentBinaryChild.right
        return binaryNode

    # Decodes your binary tree to an N-ary tree.
    def decode(self, root: 'TreeNode') -> 'NaryNode':
        if root is None:
            return None
        # Create corresponding N-ary node.
        naryNode = NaryNode(root.val, [])
        # Use the left pointer to recover the child list.
        binaryChild = root.left
        while binaryChild:
            # Recursively decode the binary subtree for each child.
            naryNode.children.append(self.decode(binaryChild))
            binaryChild = binaryChild.right
        return naryNode