Encode N-ary Tree to Binary Tree - Solution & Explanation

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.