LeetCode 431: Encode N-ary Tree to Binary Tree

Problem Restatement

We need to design a way to convert an N-ary tree into a binary tree and then reconstruct the original N-ary tree.

Two methods are required:

The conversion must preserve the full tree structure.

An N-ary tree node can have any number of children.

A binary tree node can only have:

So the main challenge is representing multiple N-ary children using only two binary pointers.

The official problem asks us to design the encoding and decoding logic ourselves. Any correct reversible representation is accepted. (leetcode.com)

Input and Output

Typical node definitions:

N-ary node:

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

Binary tree node:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Examples

Consider this N-ary tree:

        1
      / | \
     2  3  4
       / \
      5   6

We encode it into this binary tree:

        1
       /
      2
       \
        3
       / \
      5   4
       \
        6

This representation follows two rules:

For node 1:

1.left = 2

because 2 is the first child.

Then siblings are chained through right:

2.right = 3
3.right = 4

For node 3:

3.left = 5
5.right = 6

because 5 and 6 are children of 3.

This representation is called the left-child right-sibling representation.

First Thought: Store Children in Arrays

One idea is to store child lists separately or use additional metadata.

However, the problem requires a pure binary tree structure.

We only have:

left
right

So the encoding must use only those two pointers.

Key Insight

The left-child right-sibling representation converts any N-ary tree into a binary tree.

The mapping is:

Suppose an N-ary node has children:

A, B, C, D

The binary representation becomes:

parent.left = A
A.right = B
B.right = C
C.right = D

So:

1. The binary left pointer moves downward into children.
2. The binary right pointer moves sideways across siblings.

This transforms arbitrary branching into a standard binary tree.

Algorithm

Encoding

For an N-ary node:

1. Create a binary node with the same value.
2. If the node has children:
   • Encode the first child and store it in left.
3. For the remaining children:
   • Chain them through right.

Decoding

For a binary node:

1. Create an N-ary node with the same value.
2. Traverse the binary left subtree:
   • The left child is the first N-ary child.
3. Follow right pointers:
   • Each right sibling becomes another N-ary child.
4. Recursively decode each child.

Correctness

During encoding, every N-ary node becomes exactly one binary node with the same value.

For any N-ary node, its first child is stored in the binary left pointer. Every remaining child is linked through successive binary right pointers. Therefore, the full ordered child list is preserved.

Suppose an N-ary node has children:

c1, c2, c3

The encoded binary structure becomes:

left -> c1
c1.right -> c2
c2.right -> c3

This preserves both child membership and sibling order.

During decoding, we reverse this exact process. The binary left pointer identifies the first child. Following right pointers reconstructs the remaining siblings in order.

Because encoding preserves every node value and every parent-child relationship, and decoding reverses the same transformation exactly, the decoded tree is identical to the original N-ary tree.

Complexity

Here, n is the number of nodes.

h is the maximum tree height.

Implementation

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

        binary_root = TreeNode(root.val)

        if not root.children:
            return binary_root

        binary_root.left = self.encode(root.children[0])

        current = binary_root.left

        for child in root.children[1:]:
            current.right = self.encode(child)
            current = current.right

        return binary_root

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

        nary_root = Node(data.val, [])

        current = data.left

        while current:
            nary_root.children.append(self.decode(current))
            current = current.right

        return nary_root

Code Explanation

The encoder handles the empty tree first:

if not root:
    return None

Then we create the binary node:

binary_root = TreeNode(root.val)

The values are copied directly.

If the N-ary node has children:

if not root.children:
    return binary_root

we encode the first child into the binary left pointer:

binary_root.left = self.encode(root.children[0])

Then we connect the remaining siblings through right pointers:

current = binary_root.left

For every later child:

current.right = self.encode(child)
current = current.right

This creates the sibling chain.

The decoder reverses the process.

We create the N-ary node:

nary_root = Node(data.val, [])

Then we move into the first child using:

current = data.left

While siblings exist:

while current:

we decode each sibling subtree and append it into the children list:

nary_root.children.append(self.decode(current))

Then we move sideways through sibling links:

current = current.right

Eventually, all children are reconstructed in order.

Testing

We can test by encoding and then decoding trees and comparing the final structure.

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def same_nary(a, b):
    if a is None or b is None:
        return a is b

    if a.val != b.val:
        return False

    if len(a.children) != len(b.children):
        return False

    for x, y in zip(a.children, b.children):
        if not same_nary(x, y):
            return False

    return True

def run_tests():
    codec = Codec()

    root = Node(1, [
        Node(2),
        Node(3, [
            Node(5),
            Node(6),
        ]),
        Node(4),
    ])

    binary = codec.encode(root)
    restored = codec.decode(binary)

    assert same_nary(root, restored)

    single = Node(10)
    assert same_nary(
        single,
        codec.decode(codec.encode(single)),
    )

    assert codec.encode(None) is None
    assert codec.decode(None) is None

    chain = Node(1, [
        Node(2, [
            Node(3, [
                Node(4),
            ]),
        ]),
    ])

    assert same_nary(
        chain,
        codec.decode(codec.encode(chain)),
    )

    print("all tests passed")

run_tests()

Test meaning: