⚡Flashcard Drill➔
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

  1. The root is the only node that never appears as anyone's child.
  2. Collect every node that appears in some children list, then find the node absent from that set.
  3. Node objects are hashable by identity in Python, so a set of objects works directly.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems