How hard is LeetCode 1506. Find Root of N-Ary Tree?

LeetCode 1506. Find Root of N-Ary Tree is rated Medium on LeetCode.

What is the time complexity of LeetCode 1506. Find Root of N-Ary Tree?

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

What is the space complexity of LeetCode 1506. Find Root of N-Ary Tree?

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

What topics does LeetCode 1506. Find Root of N-Ary Tree cover?

LeetCode 1506. Find Root of N-Ary Tree is tagged Bit Manipulation, Tree, Depth-First Search and Hash Table on LeetCode.

Is LeetCode 1506. Find Root of N-Ary Tree a premium problem?

Yes. LeetCode 1506. Find Root of N-Ary Tree is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Find Root of N-Ary Tree — LeetCode 1506 Python Solution

MediumLeetCode PremiumBit ManipulationTreeDepth-First SearchHash Table

Problem: #1506
Pattern: Bit Manipulation
Reading time: 3 min
Source: leetcode.com

The problem

You are given all the nodes of an N-ary tree as an array of Node objects, where each node has a unique value. Return the root of the N-ary tree.

Example

Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.

Python solution

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""


class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':
        x = 0
        for node in tree:
            x ^= node.val
            for child in node.children:
                x ^= child.val
        return next(node for node in tree if node.val == x)

Complexity

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

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1506. Find Root of N-Ary Tree is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1506. Find Root of N-Ary Tree?: LeetCode 1506. Find Root of N-Ary Tree is rated Medium on LeetCode.
What is the time complexity of LeetCode 1506. Find Root of N-Ary Tree?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1506. Find Root of N-Ary Tree?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1506. Find Root of N-Ary Tree cover?: LeetCode 1506. Find Root of N-Ary Tree is tagged Bit Manipulation, Tree, Depth-First Search and Hash Table on LeetCode.
Is LeetCode 1506. Find Root of N-Ary Tree a premium problem?: Yes. LeetCode 1506. Find Root of N-Ary Tree is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.