NeetCode #410LC-1506MediumTreesNC Algo100
← Back to All Problems#410 · #1506 · Find Root of N-Ary Tree(找到 N 叉树的根节点)
📌 Problem Statement & Constraints
You are given all the nodes of an N-ary tree as an array. Each node has a unique value and a
children list. Return the root of the tree. Constraints: the number of nodes is in [1, 5 * 10^4], 1 <= Node.val <= 5 * 10^4.💡 Core Algorithmic Approaches
- The root is the only node that never appears as anyone's child.
- Collect every node that appears in some
childrenlist, then find the node absent from that set. - Node objects are hashable by identity in Python, so a set of objects works directly.
- This is O(n) and needs no traversal of the tree structure.
💻 Benchmark Python3 Implementation
class Solution:
def findRoot(self, tree: "List[Node]") -> "Node":
children = set()
for node in tree:
for c in node.children:
children.add(c) # identity-based membership
for node in tree:
if node not in children: # never a child -> the root
return node
return None⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass over the nodes and their children.
💾 Space Complexity
O(n) for the set of children.
⚠️ Interview Pitfalls & Follow-ups
- Using values instead of node objects: values are unique here so it would work, but identity is the direct statement of the property.
- Traversing the tree to find the root: you do not have a starting point, which is the whole difficulty of the problem.
- Forgetting that a node may appear as a child only once: the set handles it either way.
- Assuming the array is ordered: it is not; the root may be anywhere.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.