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, Mar 03 '17 at 21:03
You know that you can't use the same key with different elements in dict, right ? ;) — Nir Alfasi, Mar 03 '17 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, Mar 03 '17 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?_**](http://stackoverflow.com/questions/635483/what-is-the-best-way-to-implement-nested-dictionaries) — martineau, Mar 03 '17 at 21:07
I have edited the question to provide some sample data, it is not in order to begin with — ragardner, Mar 03 '17 at 21:14
This seems too broad. How is the root node identified? Is this a binary tree or some other format? — glibdud, Mar 03 '17 at 21:15
The root node would be identified I guess by pushing it to the top level as the Tree is built, if the only way to do this is with classes perhaps an expert could let me know? If so I need help printing out the contents of a Tree object... lol — ragardner, Mar 03 '17 at 21:19

Willem Van Onsem · Accepted Answer · 2017-03-03T21:33:47.397

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 03 '17 at 21:33

answered Mar 03 '17 at 21:18

Willem Van Onsem

443,496
30
428
555

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 – ragardner Mar 03 '17 at 21:32
1

@new_to_coding: you are right. I've found the bug. Now it should work. – Willem Van Onsem Mar 03 '17 at 21:34
This is this correct, thank you very much for your help ! – ragardner Mar 03 '17 at 21:37
@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': {}} – star Jan 13 '21 at 10:56
1

@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. – Willem Van Onsem Jan 13 '21 at 12:12
@Willem Van Onsem i understood now ,its the first time i'm seeing this kind of reference update using dictionary , this code deserves to be put in a frame for be so simple yet effective compared to other approaches .If possible please share any link/resource that motivated you of creating a tree with this approach. thanks a lot – star Jan 13 '21 at 14:01

Recursively creating a tree hierarchy without using class/object

1 Answers1

Linked