Recursively creating a tree hierarchy without using class/object

Question

I am having trouble creating a tree hierarchy in Python 3. I'd like to be able to do this without using classes.

The data I need to start with is not in order and in the format ['ID','Parent']:

data=[['E1', 'C1'],['C1', 'P1'],['P1', 'R1'],['E2', 'C2'],['C2', 'P2'],['P2', 'R1'],['C3', 'P2'],['E3', 'C4'],['C4', 'P3'],
  ['P3', 'R2'],['C5', 'P3'],['E4', 'C6'],['C6', 'P4'], ['P4', 'R2'],['E5', 'C7'],['C7', 'P5'],['P5', 'R3'],['E6', 'C9'],['C9', 'P6'],['P6', 'R3'],
  ['C8', 'P6'],['E7', 'C10'],['C10', 'P7'],['P7', 'R4'],['C11', 'P7'],['E8', 'C12'],['C12', 'P8'],['P8', 'R4']]

I want to create the (Tree) dictionary variable without the use of classes and end up with something like:

Tree={'R1':{'P1':{},'P2':{}},'R2':{}} etc

OR

Tree={'R1':[{'P1':[],'P2':[]}],'R2':[]} etc

Obviously R1 and R2 have more children than that but perhaps that's what the Tree structure would look like?

Is anything known about the order in which the elements in the data appear? — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Mar 3, 2017 at 21:03
You know that you can't use the same key with different elements in dict, right ? ;) — Nir Alfasi
– Nir Alfasi, Commented Mar 3, 2017 at 21:03
Python dictionaries must have unique keys. If you try to define something like {'ID': 1, 'ID': 2}, you will end up with {'ID': 2} because the second 'ID' will overwrite the first one. — Patrick Haugh
– Patrick Haugh, Commented Mar 3, 2017 at 21:04
Not sure what you have against classes because that's what a dict is—and it's fairly easy to create a dict subclass that would make doing what you want to do very easy. See What is the best way to implement nested dictionaries? — martineau
– martineau, Commented Mar 3, 2017 at 21:07
I have edited the question to provide some sample data, it is not in order to begin with — ragardner
– ragardner, Commented Mar 3, 2017 at 21:14

willeM_ Van Onsem · Accepted Answer · 2017-03-03 21:33:47Z

5

You can simply iterate over every child,parent tuple, create dictionary that maps the id's of the child and the parent to a list that contains the children of these elements. We keep doing this until we are done.

roots = set()
mapping = {}
for child,parent in data:
    childitem = mapping.get(child,None)
    if childitem is None:
        childitem =  {}
        mapping[child] = childitem
    else:
        roots.discard(child)
    parentitem = mapping.get(parent,None)
    if parentitem is None:
        mapping[parent] = {child:childitem}
        roots.add(parent)
    else:
        parentitem[child] = childitem

Now that we have done that, roots is a set of the ids of the tree roots: so for each such element we know that there is no id that is a parent. For each id in the roots, we can simply fetch from the mapping and that is a dictionary of the structure {'childid':child} where childid is the id (here a string) and child is again a dictionary of that form.

So you can print them like:

for root in roots:
    print(mapping[root])

So in your case, the tree is:

tree = { id : mapping[id] for id in roots }

For your sample data, it generates:

>>> tree
{'R1': {'P1': {'C1': {'E1': {}}}, 'P2': {'C2': {'E2': {}}, 'C3': {}}}, 'R2': {'P4': {'C6': {'E4': {}}}, 'P3': {'C5': {}, 'C4': {'E3': {}}}}, 'R3': {'P6': {'C8': {}, 'C9': {'E6': {}}}, 'P5': {'C7': {'E5': {}}}}, 'R4': {'P8': {'C12': {'E8': {}}}, 'P7': {'C11': {}, 'C10': {'E7': {}}}}}

edited Mar 3, 2017 at 21:33

answered Mar 3, 2017 at 21:18

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

ragardner Over a year ago

thank you for your input, but the output tree seems to be incomplete, for example P4 should have child C6 and IDs such as C9 are missing, many are missing in fact

willeM_ Van Onsem Over a year ago

@new_to_coding: you are right. I've found the bug. Now it should work.

ragardner Over a year ago

This is this correct, thank you very much for your help !

star Over a year ago

@WillemVanOnsem .mapping dict is getting updated automatically ,can you tell how its done sample : data=[['B', 'A'],['C', 'B']] 1st iteration : mapping={'B': {}, 'A': {'B': {}}} 2nd iteration : parentitem={} after last line of code was executed ,i was expecting parentitem only to change parentitem={'C': {}} The wiered behavious was mapping also got changed automatically even though the last line of code did not manully update the mapping dict how this is working ? how did the mapping dict got changed automatically ? mapping={'B': {'C': {}}, 'A': {'B': {'C': {}}}, 'C': {}}

willeM_ Van Onsem Over a year ago

@star: you look in the roots to obtain the root parents, so at the end roots only contains A. The other one is not updated automatically, these are simply two references to the same dictionary, so if we update that dictionary, we see this update at all the locations where we use that dictionary.

|

Collectives™ on Stack Overflow

Recursively creating a tree hierarchy without using class/object

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related