Encode N-ary Tree to Binary Tree

hard tree design

Problem

Design encode and decode functions to convert an n-ary tree to a binary tree and back losslessly.

InputN-ary: 1 → [3, 2, 4]; 3 → [5, 6]

Outputbinary: root.left = 3; 3.left = 5; 5.right = 6; 3.right = 2; 2.right = 4.

Children become a chain hanging off the left child via right-sibling links.

n-ary (val,kids val,kids …)

class Codec:
    def encode(self, root):
        if not root: return None
        b = BinaryNode(root.val)
        if root.children:
            b.left = self.encode(root.children[0])
        cur = b.left
        for child in root.children[1:]:
            cur.right = self.encode(child)
            cur = cur.right
        return b
    def decode(self, root):
        if not root: return None
        n = Node(root.val, [])
        cur = root.left
        while cur:
            n.children.append(self.decode(cur))
            cur = cur.right
        return n

class Codec {
  encode(root) {
    if (!root) return null;
    const b = { val: root.val, left: null, right: null };
    if (root.children.length) b.left = this.encode(root.children[0]);
    let cur = b.left;
    for (let i = 1; i < root.children.length; i++) {
      cur.right = this.encode(root.children[i]);
      cur = cur.right;
    }
    return b;
  }
  decode(root) {
    if (!root) return null;
    const n = { val: root.val, children: [] };
    let cur = root.left;
    while (cur) { n.children.push(this.decode(cur)); cur = cur.right; }
    return n;
  }
}

class Codec {
    public TreeNode encode(Node root) {
        if (root == null) return null;
        TreeNode b = new TreeNode(root.val);
        if (!root.children.isEmpty()) b.left = encode(root.children.get(0));
        TreeNode cur = b.left;
        for (int i = 1; i < root.children.size(); i++) {
            cur.right = encode(root.children.get(i));
            cur = cur.right;
        }
        return b;
    }
    public Node decode(TreeNode root) {
        if (root == null) return null;
        Node n = new Node(root.val, new ArrayList<>());
        TreeNode cur = root.left;
        while (cur != null) { n.children.add(decode(cur)); cur = cur.right; }
        return n;
    }
}

class Codec {
public:
    TreeNode* encode(Node* root) {
        if (!root) return nullptr;
        TreeNode* b = new TreeNode(root->val);
        if (!root->children.empty()) b->left = encode(root->children[0]);
        TreeNode* cur = b->left;
        for (int i = 1; i < (int)root->children.size(); i++) {
            cur->right = encode(root->children[i]);
            cur = cur->right;
        }
        return b;
    }
    Node* decode(TreeNode* root) {
        if (!root) return nullptr;
        Node* n = new Node(root->val, {});
        TreeNode* cur = root->left;
        while (cur) { n->children.push_back(decode(cur)); cur = cur->right; }
        return n;
    }
};

Explanation

An n-ary node can have many children, but a binary node has only a left and a right. The classic trick to squeeze one into the other is left-child / right-sibling: use left to point at the first child, and use right to chain siblings together.

So when we encode a node, we hang its first child off b.left. Then every remaining child is linked one after another through right pointers, forming a sibling chain. Each child is encoded recursively the same way.

To decode, we reverse the reading: a binary node's left is the first n-ary child, and from there we keep following right to gather all the siblings back into a children list.

This mapping is lossless because "first child" and "next sibling" together describe exactly the original parent/child relationships — nothing is lost or merged.

Example: n-ary 1 → [3, 2, 4] and 3 → [5, 6] becomes binary root.left = 3, then 3.right = 2, 2.right = 4 for the siblings, while inside 3 we get 3.left = 5 and 5.right = 6.

Time: O(n) Space: O(n)