How hard is LeetCode 431. Encode N-ary Tree to Binary Tree?

LeetCode 431. Encode N-ary Tree to Binary Tree is rated Hard on LeetCode.

What is the time complexity of LeetCode 431. Encode N-ary Tree to Binary Tree?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 431. Encode N-ary Tree to Binary Tree?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 431. Encode N-ary Tree to Binary Tree cover?

LeetCode 431. Encode N-ary Tree to Binary Tree is tagged Tree, Depth-First Search, Breadth-First Search, Design and Binary Tree on LeetCode.

Is LeetCode 431. Encode N-ary Tree to Binary Tree a premium problem?

Yes. LeetCode 431. Encode N-ary Tree to Binary Tree is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Encode N-ary Tree to Binary Tree — LeetCode 431 Python Solution

HardLeetCode PremiumTreeDepth-First SearchBreadth-First SearchDesignBinary Tree

Problem: #431
Pattern: Tree Traversal
Reading time: 9 min
Source: leetcode.com

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.

Example

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

Python solution

Python

"""
# 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))

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 431. Encode N-ary Tree to Binary Tree is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 431. Encode N-ary Tree to Binary Tree?: LeetCode 431. Encode N-ary Tree to Binary Tree is rated Hard on LeetCode.
What is the time complexity of LeetCode 431. Encode N-ary Tree to Binary Tree?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 431. Encode N-ary Tree to Binary Tree?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 431. Encode N-ary Tree to Binary Tree cover?: LeetCode 431. Encode N-ary Tree to Binary Tree is tagged Tree, Depth-First Search, Breadth-First Search, Design and Binary Tree on LeetCode.
Is LeetCode 431. Encode N-ary Tree to Binary Tree a premium problem?: Yes. LeetCode 431. Encode N-ary Tree to Binary Tree is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.