Encode N-ary Tree to Binary Tree

Hard · Graphs · Explanation and code example

DFS (Depth-First Search) Traversal

How it works

DFS offers a more elegant recursive solution using the same left-child right-sibling encoding. For each N-ary node, we recursively encode its first child and attach it as the left child of the binary node. The remaining children are encoded and linked as right siblings of the first child. Decoding reverses this: we traverse the left child's right chain to rebuild the children list.

Steps

Encode:

If the root is null, return null.
Create a binary node with the root's value.
Recursively encode the first child and set it as left.
For remaining children, recursively encode each and chain them as right siblings.
Return the binary node.

Decode:

If the root is null, return null.
Create an N-ary node with the root's value and an empty children list.
Start at the binary node's left child.
While the current sibling exists:
- Recursively decode it and add to the children list.
- Move to the right sibling.
Return the N-ary node.

Complexity

Time complexity: O(N)
Space complexity: O(D)
- Since D is proportional to N in the worst case, we could further generalize the space complexity to O(N)
- Unlike the BFS algorithm, we don't use the queue data structure in the DFS algorithm. However, implicitly the algorithm would consume more space in the function call stack due to the recursive function calls.
- And this consumption of call stack space is the main space complexity for our DFS algorithm. As we can see, the size of the call stack at any moment is exactly the number of level where the currently visited node resides, e.g. for the root node (level 0), the recursive call stack is empty.

Where N is the number of nodes in the N-ary tree, and D is the depth of the N-ary tree.

Things to watch for

Confusing Left-Child and Right-Sibling Roles

In the encoding scheme, left points to the first child of the N-ary node, while right links siblings together. A common mistake is reversing these roles or using right for children, which breaks the bidirectional mapping and makes decoding impossible.

Not Initializing the Children List

When decoding, the N-ary node's children list must be initialized as an empty list, not null or None. Many online judges expect an empty list for leaf nodes, and failing to initialize causes null pointer exceptions when appending children.

Forgetting to Handle the Empty Tree Case

Both encode and decode must handle null input and return null. Forgetting this base case causes null pointer exceptions when the root is null, as the algorithm tries to access properties of a non-existent node.

Incorrect Sibling Chain Traversal During Decode

When decoding, you must traverse the entire right-sibling chain starting from the left child. A common mistake is only processing the immediate left child without following the right pointers, which loses all siblings after the first child.

Python code example

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

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

class Codec:

    def encode(self, root):
        """Encodes an n-ary tree to a binary tree.
        """
        if not root:
            return None

        rootNode = TreeNode(root.val)
        if len(root.children) > 0:
            firstChild = root.children[0]
            rootNode.left = self.encode(firstChild)

        # the parent for the rest of the children
        curr = rootNode.left

        # encode the rest of the children
        for i in range(1, len(root.children)):
            curr.right = self.encode(root.children[i])
            curr = curr.right

        return rootNode


    def decode(self, data):
        """Decodes your binary tree to an n-ary tree.
        """
        if not data:
            return None

        rootNode = Node(data.val, [])

        curr = data.left
        while curr:
            rootNode.children.append(self.decode(curr))
            curr = curr.right

        return rootNode

C++ code example

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Codec {
public:
    // Encodes an n-ary tree to a binary tree.
    TreeNode* encode(Node* root) {
        if (!root) {
            return nullptr;
        }

        TreeNode* rootNode = new TreeNode(root->val);

        if (root->children.size() > 0) {
            Node* firstChild = root->children[0];
            rootNode->left = encode(firstChild);
        }

        // the parent for the rest of the children
        TreeNode* curr = rootNode->left;

        // encode the rest of the children
        for (int i = 1; i < root->children.size(); i++) {
            curr->right = encode(root->children[i]);
            curr = curr->right;
        }

        return rootNode;
    }

    // Decodes your binary tree to an n-ary tree.
    Node* decode(TreeNode* root) {
        if (!root) {
            return nullptr;
        }

        Node* rootNode = new Node(root->val);

        TreeNode* curr = root->left;
        while (curr) {
            rootNode->children.push_back(decode(curr));
            curr = curr->right;
        }

        return rootNode;
    }
};

Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations