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:

Method	Meaning
`encode(root)`	Convert an N-ary tree into a binary tree
`decode(root)`	Convert the binary tree back into the original N-ary tree

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:

Pointer	Meaning
`left`	Left child
`right`	Right child

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.

Input and Output

Item	Meaning
Input to `encode`	Root of an N-ary tree
Output from `encode`	Root of a binary tree
Input to `decode`	Root of the encoded binary tree
Output from `decode`	Original N-ary tree
Empty tree	Encode and decode as `None`

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:

We encode it into this binary tree:

This representation follows two rules:

Binary Pointer	Meaning
`left`	First child
`right`	Next sibling

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:

N-ary Meaning	Binary Pointer
first child	`left`
next sibling	`right`

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:

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

This transforms arbitrary branching into a standard binary tree.

Algorithm

Encoding

For an N-ary node:

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

Decoding

For a binary node:

Create an N-ary node with the same value.
Traverse the binary left subtree:
- The left child is the first N-ary child.
Follow right pointers:
- Each right sibling becomes another N-ary child.
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

Metric	Value	Why
Time	`O(n)`	Every node is processed once
Space	`O(h)`	Recursion depth follows tree height

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:

Test	Why
Multi-child tree	Checks sibling encoding
Nested subtree	Checks recursive structure
Single node	Checks smallest tree
Empty tree	Checks `None` handling
Deep chain	Checks recursive depth