⚡Flashcard Drill➔
NeetCode #415LC-431HardTreesNC Algo100
← Back to All Problems

#415 · #431 · Encode N-ary Tree to Binary Tree(将 N 叉树编码为二叉树)

📌 Problem Statement & Constraints

Design an algorithm to convert an N-ary tree into a binary tree and back. The binary tree must follow the left-child, right-sibling representation. Constraints: the number of nodes is in [0, 10^4], 0 <= Node.val <= 10^4, the depth is at most 1000.

💡 Core Algorithmic Approaches

  1. The left-child/right-sibling encoding maps an N-ary node to a binary node whose left pointer is the first child and whose right pointer is the next sibling.
  2. Encoding: create a binary node, encode the first child as left, then chain the remaining children along the right pointers of that left subtree.
  3. Decoding: the left subtree is the first child, and following right pointers from it enumerates the siblings.
  4. The mapping is a bijection, so the round trip is exact.

💻 Benchmark Python3 Implementation

class Codec:
    def encode(self, root: "Optional[Node]") -> Optional[TreeNode]:
        if not root:
            return None
        node = TreeNode(root.val)
        if root.children:
            node.left = self.encode(root.children[0])   # first child
        # chain the remaining children as right siblings
        cur = node.left
        for c in root.children[1:]:
            cur.right = self.encode(c)
            cur = cur.right
        return node

    def decode(self, data: Optional[TreeNode]) -> "Optional[Node]":
        if not data:
            return None
        node = Node(data.val, [])
        cur = data.left                     # first child
        while cur:
            node.children.append(self.decode(cur))
            cur = cur.right                 # next sibling
        return node

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) for both directions.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Putting all children on the left spine: only the first child goes to left; the rest are siblings reached via right.
  • Forgetting to advance cur: all siblings would overwrite the same right pointer.
  • Decoding the right pointers as children: they represent siblings, so they must be appended to the same parent's children list.
  • Assuming the round trip preserves node identity: only the structure and values are preserved.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems