CODEWITHSUNDEEP
pythondictionarytreeroot
Chipleader
Chipleader

Reputation: 13

Find root in dictionary-tree

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?

Upvotes: 1

Views: 944

Answers (2)

solub
solub

Reputation: 1363

In your example the variables (a, b, c, e) are not defined. Assuming you can replace them by strings (or even integers):

d = {'b':['e'], 'a':['b','c'], 'c':[], 'e':[]}

root = set(d).difference(*d.values()).pop()
print(root)

--> a

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726569

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 }

Upvotes: 1

Related Questions