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:
[0, 104].0 <= Node.val <= 1041000Problem 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.
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.
Python
Java
C++
Go
TypeScript
| 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 |
encode N-ary Tree To Binary Tree • Owen Wu • 108 views views
Practice Encode N-ary Tree to Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor