Find root in dictionary-tree

Question

I have a dictionary-tree like this:

{ b : [e], a : [b,c], c : [], e : []}

How can I find the root(in this example 'a`) fast even if I have a very long dictionary?

Answer 1

Walk the adjacency list, put each "from" node into a set of source nodes, and each of its corresponding "to" nodes into a set of destination nodes.

Subtracting the set of destinations from the set of sources will yield one of the following:

• An empty set - this means that your adjacency list does not represent a tree or a forest,
• A set with multiple nodes - this means that your adjacency list represents a forest, or
• A set with a single item - this is the root of the tree represented by your adjacency list.

Here is how this works for your example:

• source: { b, a, c, e }
• destination: { e, b, c }
• source \ destination: { a }