LeetCode 431: Encode N-ary Tree to Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 431: Encode N-ary Tree to Binary Tree?

In LeetCode 431: Encode N-ary Tree to Binary Tree, you’re given two tasks: 1. Encode: Convert an N-ary tree (where each Node has a value val and a list of children children) into a binary tree (where each TreeNode has val, left, and right). 2. Decode: Convert the binary tree back into the original N-ary tree. An N-ary tree allows any number of children per node, unlike a binary tree’s limit of two. For example, an N-ary tree with root 1, children [2, 3, 4], and 3’s children [5, 6] needs a binary encoding—perhaps 1’s left is 2, 2’s right is 3, 3’s right is 4, and 3’s left is 5 with 5’s right as 6—then decoded back perfectly. The encoding must preserve the structure for accurate reconstruction.

Problem Statement

• Input:
• Encode: A Node (root of N-ary tree).
• Decode: A TreeNode (root of binary tree).
• Output:
• Encode: A TreeNode (root of binary tree).
• Decode: A Node (root of N-ary tree).
• Rules:
• Encode N-ary tree into binary tree.
• Decode binary tree back to original N-ary tree.
• Use provided Node and TreeNode classes.

Constraints

• Number of nodes is in range [0, 10⁴].
• 0 <= Node.val <= 10⁴.
• Values may not be unique.

Examples

• Input: [1,null,2,3,4,null,5,6]
• Encode: Binary tree (e.g., 1.left = 2, 2.right = 3, 3.right = 4, 3.left = 5, 5.right = 6).
• Decode: Original N-ary tree: 1, children [2, 3, 4], 3’s children [5, 6].
• Input: [1,null,3,null,2]
• Encode: 1.left = 3, 3.left = 2.
• Decode: 1, children [3], 3’s child [2].
• Input: []
• Encode/Decode: None.

Understanding the Problem: Reshaping the Tree

To solve LeetCode 431: Encode N-ary Tree to Binary Tree in Python, we need to: 1. Encode: Transform an N-ary tree into a binary tree, preserving all info. 2. Decode: Reverse the process to restore the N-ary tree. A naive idea might be to just dump all children into left—but we’d lose the multi-child structure! We’ll use:

• Best Solution (Left-Child Right-Sibling Encoding): O(n) time, O(h) space—reshapes efficiently.
• Alternative Solution (Serialized String Approach): O(n) time, O(n) space—flattens and rebuilds.

Let’s dive into the left-child right-sibling solution with a clear, step-by-step explanation.

Best Solution: Left-Child Right-Sibling Encoding

Why This Is the Best Solution

The left-child right-sibling encoding method is the top pick because it’s efficient—O(n) time for both encode and decode, O(h) space (h = height)—and elegantly maps N-ary children into a binary structure using a standard technique: the first child goes to left, and subsequent siblings chain via right. It decodes by reversing this pattern, collecting siblings into a list. It’s like threading N-ary kids into a binary chain, then unthreading them back into a family!

How It Works

Encode

• Step 1: For each node:
• If no children, return a binary TreeNode with val, no kids.
• If children exist:
• left = first child (recursively encoded).
• Chain remaining children via right (siblings).
• Step 2: Return binary root.

Decode

• Step 1: Start at binary root.
• Step 2: For each node:
• Create N-ary Node with val.
• Collect children: follow left to first child, then right for siblings.
• Recurse on each child’s left.
• Step 3: Return N-ary root.

Why It Works

• Left-child right-sibling preserves all N-ary info in binary form.
• Recursive encoding/decoding ensures O(n) time, minimal space.
• It’s like folding a fan into a stick, then unfolding it back!

Step-by-Step Example

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

• N-ary Tree:

1 /|\ 2 3 4 / \ 5 6

• Encode:
• Node 1: Children [2, 3, 4].
• Left = 2 (TreeNode(2)).
• 2.right = 3 (TreeNode(3)).
• 3.right = 4 (TreeNode(4)).
• 3.left = 5 (TreeNode(5)), 5.right = 6 (TreeNode(6)).
• Binary Tree:

1 / 2 \ 3 / \ 5 4 \ 6

• Decode:
• Root 1: Left = 2.
• Node 2: No left, siblings [3].
• Node 3: Left = 5, siblings [4], 5’s sibling [6].
• Result: Original N-ary tree.

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 []

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

class Codec:
    def encode(self, root: 'Node') -> 'TreeNode':
        if not root:
            return None

        # Step 1: Create binary root
        binary_root = TreeNode(root.val)

        # Step 2: Encode children
        if root.children:
            # First child to left
            binary_root.left = self.encode(root.children[0])
            # Chain siblings to right
            curr = binary_root.left
            for child in root.children[1:]:
                curr.right = self.encode(child)
                curr = curr.right

        return binary_root

    def decode(self, root: 'TreeNode') -> 'Node':
        if not root:
            return None

        # Step 1: Create N-ary root
        nary_root = Node(root.val)

        # Step 2: Decode children
        if root.left:
            # First child from left
            nary_root.children.append(self.decode(root.left))
            # Siblings from right chain
            curr = root.left.right
            while curr:
                nary_root.children.append(self.decode(curr))
                curr = curr.right

        return nary_root

• Line 2-6: N-ary Node class (given):
• val, children (list of kids).
• Line 9-13: Binary TreeNode class (given):
• val, left, right.
• Encode:
• Line 18-20: Handle empty root, return None.
• Line 23: Create binary node with val.
• Line 26-32: Encode children:
• Line 27-28: If kids, left = first child (recursed).
• Line 30-32: Chain others via right (siblings).
• Line 34: Return binary root.
• Decode:
• Line 38-40: Handle empty root, return None.
• Line 43: Create N-ary node with val.
• Line 46-52: Decode children:
• Line 47-48: If left, append first child (recursed).
• Line 50-52: Follow right chain, append siblings.
• Line 54: Return N-ary root.
• Time Complexity: O(n)—each node processed once.
• Space Complexity: O(h)—recursion stack, h = height.

This is like folding an N-ary fan into a binary stick and unfolding it back!

Alternative Solution: Serialized String Approach

Why an Alternative Approach?

The serialized string approach first flattens the N-ary tree into a string (e.g., preorder with child counts), then rebuilds it as a binary tree, and reverses the process. It’s O(n) time and O(n) space—explicit but memory-heavy due to string storage. It’s like writing the tree as a message, then parsing it into binary form!

How It Works

Encode

• Serialize N-ary tree to string (e.g., "1,3,2,0,3,2,5,0,6,0,4,0").
• Parse string into binary tree with values and structure.

Decode

• Serialize binary tree back to string.
• Reconstruct N-ary tree from string.

Step-by-Step Example

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

• Serialize: "1,3,2,0,3,2,5,0,6,0,4,0".
• Encode: Binary tree (e.g., store string as nodes or parse directly).
• Decode: Reverse to N-ary tree.

Code for Serialized Approach (Simplified)

Copy codeclass Codec:
    def serialize_nary(self, root):
        if not root:
            return ""
        result = [str(root.val), str(len(root.children))]
        for child in root.children:
            result.extend(self.serialize_nary(child))
        return ",".join(result)

    def encode(self, root: 'Node') -> 'TreeNode':
        if not root:
            return None
        serialized = self.serialize_nary(root)
        nodes = serialized.split(",")
        def build_binary(idx):
            if idx >= len(nodes):
                return None, idx
            node = TreeNode(int(nodes[idx]))
            idx += 1
            child_count = int(nodes[idx])
            idx += 1
            if child_count > 0:
                node.left, idx = build_binary(idx)
                curr = node.left
                for _ in range(child_count - 1):
                    curr.right, idx = build_binary(idx)
                    curr = curr.right
            return node, idx
        binary_root, _ = build_binary(0)
        return binary_root

    def decode(self, root: 'TreeNode') -> 'Node':
        if not root:
            return None
        # Simplified: assumes same serialization
        serialized = self.serialize_binary(root)
        nodes = serialized.split(",")
        def build_nary(idx):
            if idx >= len(nodes):
                return None, idx
            node = Node(int(nodes[idx]))
            idx += 1
            child_count = int(nodes[idx])
            idx += 1
            for _ in range(child_count):
                child, idx = build_nary(idx)
                node.children.append(child)
            return node, idx
        nary_root, _ = build_nary(0)
        return nary_root

    def serialize_binary(self, root):
        if not root:
            return ""
        result = [str(root.val), "1"]  # Simplified child count
        if root.left:
            result.extend(self.serialize_binary(root.left))
        if root.right:
            result.extend(self.serialize_binary(root.right))
        return ",".join(result)

• Time Complexity: O(n)—each node processed.
• Space Complexity: O(n)—string storage.

It’s a string-based reshaper!

Comparing the Two Solutions

• Left-Child Right-Sibling (Best):
• Pros: O(n), O(h), direct and lean.
• Cons: Structural mapping.
• Serialized String (Alternative):
• Pros: O(n), O(n), explicit string.
• Cons: Extra space, parsing.

Left-child right-sibling wins for efficiency.

Additional Examples and Edge Cases

• []: None.
• [1]: 1 (binary: 1).
• [1,null,2]: 1.left = 2.

Left-child handles all.

Complexity Breakdown

• Left-Child: Time O(n), Space O(h).
• Serialized: Time O(n), Space O(n).

Left-child is optimal.

Key Takeaways

• Left-Child: Chain it smart!
• Serialized: String it out!
• Trees: Structures twist.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Encode That Tree

LeetCode 431: Encode N-ary Tree to Binary Tree in Python is a tree-reshaping quest. Left-child right-sibling encoding threads it fast, while serialized string flattens it steady. Want more tree fun? Try LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List or LeetCode 589: N-ary Tree Preorder Traversal. Ready to reshape? Head to Solve LeetCode 431 on LeetCode and encode that tree today!