Encode N-ary Tree to Binary Tree solution and explanation
The 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-nary tree structure.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See following example).
For example, you may encode the following 3-ary tree to a binary tree in this way:
Input: root = [1,null,3,2,4,null,5,6]
Note that the above is just an example which might or might not work. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Example 1:
Input: root = [1,null,3,2,4,null,5,6] Output: [1,null,3,2,4,null,5,6]
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. 0 <= Node.val <= 104- 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. Your encode and decode algorithms should be stateless.
Approach overview
Problem Overview: Convert an N-ary tree (each node can have multiple children) into a binary tree and be able to decode it back without losing structure. The typical strategy maps the first child to the left pointer and the next sibling to the right pointer.
Approach 1: Left-Child Right-Sibling Recursion (O(n) time, O(h) space)
The standard solution uses the left-child right-sibling representation. For each N-ary node, create a binary node with the same value. Its first child becomes the left pointer in the binary tree. Remaining children are linked through right pointers as siblings. During encoding, iterate through the children list and recursively encode each child while chaining them through the right pointer. Decoding reverses the process: traverse the left child and follow right pointers to reconstruct the original children list. Every node is processed once, giving O(n) time with recursion stack space O(h), where h is the tree height. This approach relies heavily on Tree traversal and Depth-First Search.
Approach 2: Iterative DFS Encoding (O(n) time, O(n) space)
An iterative variation replaces recursion with an explicit stack. Push the N-ary root, create its binary equivalent, and process children sequentially. The first child becomes the binary left node, while subsequent children are chained via the right pointer. The stack stores pairs of N-ary and binary nodes to maintain the mapping during traversal. This version avoids recursion limits and behaves similarly to iterative DFS over a Binary Tree. Time complexity remains O(n) since every node is encoded once, but auxiliary stack space can reach O(n) in skewed trees.
Approach 3: Breadth-First Encoding (O(n) time, O(n) space)
A queue-based method processes nodes level by level using Breadth-First Search. For each N-ary node dequeued, build its binary counterpart and attach its children using the same left-child/right-sibling rule. Each child is enqueued for later processing. This keeps the logic explicit and avoids deep recursion, though the queue may hold many nodes at once. Complexity stays O(n) time and O(n) space.
Recommended for interviews: The recursive left-child right-sibling transformation is the expected solution. Interviewers look for the key insight that an N-ary node's first child maps to left and siblings map to right. Explaining this representation clearly shows understanding of tree design problems. Iterative variants are acceptable follow-ups but rarely the primary expectation.
Solution
We can point the left pointer of the binary tree to the first child of the N-ary tree and the right pointer of the binary tree to the next sibling node of the N-ary tree.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the N-ary tree.
"""
# Definition for a Node.
class Node:
def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
self.val = val
self.children = children
"""
"""
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
"""
class Codec:
# Encodes an n-ary tree to a binary tree.
def encode(self, root: "Optional[Node]") -> Optional[TreeNode]:
if root is None:
return None
node = TreeNode(root.val)
if not root.children:
return node
left = self.encode(root.children[0])
node.left = left
for child in root.children[1:]:
left.right = self.encode(child)
left = left.right
return node
# Decodes your binary tree to an n-ary tree.
def decode(self, data: Optional[TreeNode]) -> "Optional[Node]":
if data is None:
return None
node = Node(data.val, [])
if data.left is None:
return node
left = data.left
while left:
node.children.append(self.decode(left))
left = left.right
return node
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(root))/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Codec {
// Encodes an n-ary tree to a binary tree.
public TreeNode encode(Node root) {
if (root == null) {
return null;
}
TreeNode node = new TreeNode(root.val);
if (root.children == null || root.children.isEmpty()) {
return node;
}
TreeNode left = encode(root.children.get(0));
node.left = left;
for (int i = 1; i < root.children.size(); i++) {
left.right = encode(root.children.get(i));
left = left.right;
}
return node;
}
// Decodes your binary tree to an n-ary tree.
public Node decode(TreeNode data) {
if (data == null) {
return null;
}
Node node = new Node(data.val, new ArrayList<>());
if (data.left == null) {
return node;
}
TreeNode left = data.left;
while (left != null) {
node.children.add(decode(left));
left = left.right;
}
return node;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(root));/*
// 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 == nullptr) {
return nullptr;
}
TreeNode* node = new TreeNode(root->val);
if (root->children.empty()) {
return node;
}
TreeNode* left = encode(root->children[0]);
node->left = left;
for (int i = 1; i < root->children.size(); i++) {
left->right = encode(root->children[i]);
left = left->right;
}
return node;
}
// Decodes your binary tree to an n-ary tree.
Node* decode(TreeNode* data) {
if (data == nullptr) {
return nullptr;
}
Node* node = new Node(data->val, vector<Node*>());
if (data->left == nullptr) {
return node;
}
TreeNode* left = data->left;
while (left != nullptr) {
node->children.push_back(decode(left));
left = left->right;
}
return node;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(root));/**
* Definition for _Node.
* class _Node {
* val: number
* children: _Node[]
*
* constructor(v: number) {
* this.val = v;
* this.children = [];
* }
* }
*/
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
class Codec {
constructor() {}
// Encodes an n-ary tree to a binary tree.
serialize(root: _Node | null): TreeNode | null {
if (root === null) {
return null;
}
const node = new TreeNode(root.val);
if (root.children.length === 0) {
return node;
}
let left: TreeNode | null = this.serialize(root.children[0]);
node.left = left;
for (let i = 1; i < root.children.length; i++) {
if (left) {
left.right = this.serialize(root.children[i]);
left = left.right;
}
}
return node;
}
// Decodes your binary tree back to an n-ary tree.
deserialize(root: TreeNode | null): _Node | null {
if (root === null) {
return null;
}
const node = new _Node(root.val);
if (root.left === null) {
return node;
}
let left: TreeNode | null = root.left;
while (left !== null) {
node.children.push(this.deserialize(left));
left = left.right;
}
return node;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type Codec struct {
}
func Constructor() *Codec {
return &Codec{}
}
// Encodes an n-ary tree to a binary tree.
func (this *Codec) encode(root *Node) *TreeNode {
if root == nil {
return nil
}
node := &TreeNode{Val: root.Val}
if len(root.Children) == 0 {
return node
}
left := this.encode(root.Children[0])
node.Left = left
for i := 1; i < len(root.Children); i++ {
left.Right = this.encode(root.Children[i])
left = left.Right
}
return node
}
// Decodes your binary tree to an n-ary tree.
func (this *Codec) decode(data *TreeNode) *Node {
if data == nil {
return nil
}
node := &Node{Val: data.Val, Children: []*Node{}}
if data.Left == nil {
return node
}
left := data.Left
for left != nil {
node.Children = append(node.Children, this.decode(left))
left = left.Right
}
return node
}
/**
* Your Codec object will be instantiated and called as such:
* obj := Constructor();
* bst := obj.encode(root);
* ans := obj.decode(bst);
*/Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Left-Child Right-Sibling Recursion | O(n) | O(h) | Best general solution; concise and commonly expected in interviews |
| Iterative DFS Encoding | O(n) | O(n) | When avoiding recursion or handling deep trees |
| Breadth-First Encoding | O(n) | O(n) | Useful when processing nodes level-by-level or integrating with BFS pipelines |
Frequently asked questions
Is Encode N-ary Tree to Binary Tree easy or hard?
Encode N-ary Tree to Binary Tree is classified as Hard because it requires understanding how to redesign one tree structure into another while preserving relationships. The key insight is simple once known, but discovering the left-child right-sibling representation can be challenging during interviews.
Encode N-ary Tree to Binary Tree Python/Java solution
Most implementations use recursion. During encoding, create a binary node for each N-ary node, map the first child to the left pointer, and link siblings through right pointers. The same structure is used in Python, Java, C++, Go, and TypeScript implementations.
How to solve Encode N-ary Tree to Binary Tree in O(n)?
Traverse the N-ary tree using DFS. For each node, create a binary node, assign its first child to the left pointer, and connect the remaining children through right pointers as siblings. This left-child right-sibling mapping preserves the structure and processes each node once, giving O(n) time complexity.
What is the best approach for Encode N-ary Tree to Binary Tree?
The most common solution uses the left-child right-sibling representation. Each N-ary node's first child becomes the binary node's left pointer, and the remaining children are connected using right pointers as siblings. This approach encodes and decodes the structure with O(n) time and O(h) recursion space.
Is Encode N-ary Tree to Binary Tree asked at Google/Amazon/Meta?
Tree design and transformation problems like this appear in interviews at companies such as Google, Amazon, and Meta. They test understanding of tree representations, recursion, and the ability to transform data structures without losing structural information.
What data structure is used in Encode N-ary Tree to Binary Tree?
The solution relies on tree data structures and depth-first traversal. The key design idea is representing an N-ary tree using a binary tree with left-child and right-sibling pointers.
What is the time complexity of Encode N-ary Tree to Binary Tree?
The encoding and decoding processes both run in O(n) time because every node in the N-ary tree is visited exactly once. Auxiliary space is O(h) with recursion, where h is the tree height, or O(n) when using an explicit stack or queue.