LC: 1506. Find Root of N Ary Tree - spiralgo/algorithms GitHub Wiki

1506. Find Root of N-Ary Tree:

The Essence:

The values of nodes are unique. The problem then is to find the node with this unique value.

Details:

Unique value in an array of values can be found using the XOR operation. For each node in the nodes list, we XOR their value to some number (initially 0), then XOR their children's value to that number. Nodes that are node will be XORed twice to that number, which is equivalent to turning on and turning off the effect of their bit values on that number. Only node's value's bits will stay the same. Then simply the node with this remaining value needs to be found.