MediumNo. 1506LeetCode Premium
Find Root of N-Ary Tree — LeetCode 1506 Python Solution
- Pattern
- Bit Manipulation
- Topics
- Bit Manipulation, Tree, Depth-First Search, Hash Table
- 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
"""
# 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
- Time
- O(n)
- Space · auxiliary
- O(n)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0508 | Most Frequent Subtree Sum | Medium |
| 0652 | Find Duplicate Subtrees | Medium |
| 0653 | Two Sum IV - Input is a BST | Easy |
| 0690 | Employee Importance | Medium |
| 0863 | All Nodes Distance K in Binary Tree | Medium |
| 0865 | Smallest Subtree with all the Deepest Nodes | Medium |
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.