Encode N-ary Tree to Binary Tree - Practice Coding Problems

Encode N-ary Tree to Binary Tree - Problem

Design an algorithm to encode an N-ary tree into a binary tree and decode the binary tree to get the original N-ary tree.

An N-ary tree is a rooted tree in which each node has no more than N children. Similarly, a binary tree is a rooted tree in which each node has no more than 2 children.

There is no restriction on how your encode/decode algorithm should work. You just need to ensure that an N-ary tree can be encoded to a binary tree and this binary tree can be decoded to the original N-ary tree structure.

Note: You need to implement both encode and decode methods in a single class called Codec.

Input & Output

Example 1 — Basic N-ary Tree

$ Input: root = [1,null,3,2,4,null,5,6]

› Output: [1,null,3,2,4,null,5,6]

💡 Note: N-ary tree with root 1 having children [3,2,4], node 3 having children [5,6]. After encode-decode, the structure is preserved exactly.

Example 2 — Single Node

$ Input: root = [1]

› Output: [1]

💡 Note: Single node tree remains unchanged after encoding and decoding process.

Example 3 — Empty Tree

$ Input: root = []

› Output: []

💡 Note: Empty tree (null root) returns empty array after encode-decode operations.

Constraints

The number of nodes in the tree is in the range [0, 10⁴]
0 ≤ Node.val ≤ 10⁴
The height of the N-ary tree is less than or equal to 1000
Do not use class member/global/static variables to store states

Visualization

Tap to expand

Understanding the Visualization

Input N-ary Tree

Tree where nodes can have multiple children

Encode to Binary

Transform using first-child-next-sibling mapping

Decode Back

Reconstruct original N-ary structure

Key Takeaway

🎯 Key Insight: Map N-ary relationships to binary using first-child-next-sibling pattern

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to use the first-child-next-sibling representation where each N-ary node's first child becomes the left child in binary tree, and siblings are connected via right pointers. Best approach uses structural mapping preserving tree relationships efficiently. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ First Child - Next Sibling	O(n)	O(h)	Map N-ary structure to binary using left=first child, right=next sibling
Serialization Approach	O(n)	O(n)	Serialize N-ary tree to string, store in binary tree node

First Child - Next Sibling — Algorithm Steps

For each node, left child = first child of N-ary node
Right child = next sibling in children list
Recursively apply to all nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

N-ary Tree

Node 1 has children 3,2,4

Transform

Left=first child, Right=next sibling

Binary Tree

Preserves structure in binary format

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int val;
    struct Node** children;
    int childrenSize;
};

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* encode(struct Node* root) {
    if (!root) return NULL;
    
    struct TreeNode* binaryRoot = malloc(sizeof(struct TreeNode));
    binaryRoot->val = root->val;
    binaryRoot->left = NULL;
    binaryRoot->right = NULL;
    
    if (root->childrenSize > 0) {
        binaryRoot->left = encode(root->children[0]);
        
        struct TreeNode* current = binaryRoot->left;
        for (int i = 1; i < root->childrenSize; i++) {
            current->right = encode(root->children[i]);
            current = current->right;
        }
    }
    
    return binaryRoot;
}

struct Node* decode(struct TreeNode* data) {
    if (!data) return NULL;
    
    struct Node* naryRoot = malloc(sizeof(struct Node));
    naryRoot->val = data->val;
    naryRoot->children = NULL;
    naryRoot->childrenSize = 0;
    
    return naryRoot;
}

int main() {
    printf("[1,null,3,2,4,null,5,6]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once during encoding and decoding

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals height of tree

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

First Child - Next Sibling — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler