Encode N-ary Tree to Binary Tree

There are a lot of solutions to convert a N-ary tree to a binary tree. We only introduce one classical solution.

The strategy follows two rules:

1. The left childof each node in the binary tree is the next siblingof the node in the N-ary tree.
2. The right childof each node in the binary tree is the first childof the node in the N-ary tree.

Here is an example to help you understand this strategy:

Using this strategy, you can simply convert a N-ary tree to a binary tree recursively. Also, you can easily recover the N-ary tree from the binary tree you converted. The recursion recovery strategy for each node is:

1. Deal with its children recursively.
2. Add its left childas the next child of its parentif it has a left child.
3. Add its right childas the first child of the node itselfif it has a right child.

Here is an example to help you understand this strategy:

Leetcode Serialize

{"$id":"1","children":[{"$id":"2","children":[{"$id":"5","children":[],"val":5},
{"$id":"6","children":[],"val":6}],"val":3},{"$id":"3","children":[],"val":2},
{"$id":"4","children":[],"val":4}],"val":1}

Final Version

class Codec {
public:

    // Encodes an n-ary tree to a binary tree.
    TreeNode* encode(Node* root) {
        if (root == nullptr) return nullptr;

        TreeNode* brt = new TreeNode(root->val);
        brt->left = nullptr;

        if (root->children.size() == 0) {
            brt->right = nullptr;
            return brt;
        } else {
            brt->right = encode(root->children[0], root, 0);
            return brt;
        }
    }

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

        cout << endl;
        preBTree(root);

        vector<Node*> children;
        Node* nrt = new Node(root->val, children);
        decode(root->right, nrt);

        return nrt;
    }

private:
    TreeNode* encode(Node* root, Node* parent, int index) {
        if (root == nullptr) return nullptr;
        TreeNode* brt = new TreeNode(root->val);

        if (index + 1 < parent->children.size()) {
            brt->left = encode(parent->children[index+1], parent, index+1);
        } else {
            brt->left = nullptr;
        }

        if (root->children.size() > 0) {
            brt->right = encode(root->children[0], root, 0);
        }

        return brt;
    }

    void decode(TreeNode* root, Node* parent) {
        if (!root) return;   

        vector<Node*> children;
        Node* nrt = new Node(root->val, children);
        decode(root->right, nrt);
        parent->children.push_back(nrt);

        if(root->left) decode(root->left, parent);
    }

    void preNTree(Node* root) {
        if (!root) return;
        cout << root->val << ' ';

        for (auto it : root->children) {
            preNTree(it);
        }
    }

    void preBTree(TreeNode* root) {
        if (!root) return;
        cout << root->val << ' ';

        preBTree(root->left);
        preBTree(root->right);
    }
};

N-ary Tree to Binary Tree First version

/*
// Definition for a Node.
class Node {
public:
    int val = NULL;
    vector<Node*> children;

    Node() {}

    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 == nullptr) return nullptr;

        // preNTree(root);
        // convert root node first
        TreeNode* brt = new TreeNode(root->val);
        brt->left = nullptr;

        if (root->children.size() == 0) {
            brt->right = nullptr;
            return brt;
        //} else {
        //    brt->right = encode(parent->children[0], root, 0);
        //    return brt;
        //}
        } else if (root->children.size() == 1) {
            brt->right = new TreeNode(root->children[0]->val);
            return brt;
        } else if (root->children.size() >= 2) {
            brt->right = encode(root->children[0], root, 0);
            return brt;
        }
    }

    // Decodes your binary tree to an n-ary tree.
    Node* decode(TreeNode* root) {
        cout << endl;
        preBTree(root);
        return nullptr;

    }

private:
    TreeNode* encode(Node* root, Node* parent, int index) {
        if (root == nullptr) return nullptr;
        TreeNode* brt = new TreeNode(root->val);
        // cout << root->val << endl;
        cout << root->val << ": " << parent->children.size() << endl;

        if (index + 1 < parent->children.size()) {
            // bug: brt->left = encode(parent->children[index+1], root, index+1);
            brt->left = encode(parent->children[index+1], parent, index+1);
        } else {
            brt->left = nullptr;
        }

        if (root->children.size() > 0) {
            brt->right = encode(root->children[0], root, 0);
        }

        return brt;
    }

    void preNTree(Node* root) {
        if (!root) return;
        cout << root->val << ' ';

        for (auto it : root->children) {
            preNTree(it);
        }
    }

    void preBTree(TreeNode* root) {
        if (!root) return;
        cout << root->val << ' ';

        preBTree(root->left);
        preBTree(root->right);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(root));

Bug corner case:

class Codec {
public:

    // Encodes an n-ary tree to a binary tree.
    TreeNode* encode(Node* root) {
        if (root == nullptr) return nullptr;

        // preNTree(root);
        // convert root node first
        TreeNode* brt = new TreeNode(root->val);
        brt->left = nullptr;

        if (root->children.size() == 0) {
            brt->right = nullptr;
            return brt;
        } else {
            brt->right = encode(root->children[0], root, 0);
            return brt;
        }
        // bug: when first root children size == 1, will never call encode()
        //} else if (root->children.size() == 1) {
        //    brt->right = new TreeNode(root->children[0]->val);
        //    return brt;
        //} else if (root->children.size() >= 2) {
        //    brt->right = encode(root->children[0], root, 0);
        //    return brt;
        //}
    }

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

        cout << endl;
        preBTree(root);

        vector<Node*> children;
        Node* nrt = new Node(root->val, children);
        decode(root->right, nrt);

        return nrt;

    }

private:
    TreeNode* encode(Node* root, Node* parent, int index) {
        if (root == nullptr) return nullptr;
        TreeNode* brt = new TreeNode(root->val);

        if (index + 1 < parent->children.size()) {
            brt->left = encode(parent->children[index+1], parent, index+1);
        } else if (index + 1 == parent->children.size()) {
            brt->left = nullptr;
        } else {
            brt->left = nullptr;
        }

        if (root->children.size() > 0) {
            brt->right = encode(root->children[0], root, 0);
        }

        return brt;
    }

    void decode(TreeNode* root, Node* parent) {
        // bug: forgot return
        //if (!root)  parent->children = parent->children.push_back(nullptr);
        if (!root){
        // bug: push extra nullptr to vector, instead of empty vector as example
            //parent->children.push_back(nullptr); 
            return;
        }  
        vector<Node*> children;
        Node* nrt = new Node(root->val, children);
        decode(root->right, nrt);
        parent->children.push_back(nrt);

        if(root->left) decode(root->left, parent);
    }

    void preNTree(Node* root) {
        if (!root) return;
        cout << root->val << ' ';

        for (auto it : root->children) {
            preNTree(it);
        }
    }

    void preBTree(TreeNode* root) {
        if (!root) return;
        cout << root->val << ' ';

        preBTree(root->left);
        preBTree(root->right);
    }
};

Deserialize