Skip to content

1506. Find Root of N-Ary Tree

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  Node* findRoot(vector<Node*> tree) {
    int sum = 0;

    for (Node* node : tree) {
      sum ^= node->val;
      for (Node* child : node->children)
        sum ^= child->val;
    }

    for (Node* node : tree)
      if (node->val == sum)
        return node;

    throw;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public Node findRoot(List<Node> tree) {
    int sum = 0;

    for (Node node : tree) {
      sum ^= node.val;
      for (Node child : node.children)
        sum ^= child.val;
    }

    for (Node node : tree)
      if (node.val == sum)
        return node;

    throw new IllegalArgumentException();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def findRoot(self, tree: list['Node']) -> 'Node':
    sum = 0

    for node in tree:
      sum ^= node.val
      for child in node.children:
        sum ^= child.val

    for node in tree:
      if node.val == sum:
        return node