Python recursion to sort list of tuples into tree structure

Question

I'm new to coding and got myself stuck trying to recursively sort a list of tuples. Here is my code:

# table consists on [(code, parent), (code, parent), ...]
table = [('1', ''),
      ('1.1', '1'),
      ('2', ''),
      ('2.1','2'),
      ('2.1.1','2.1'),
      ('3',''),
      ('3.1','3'),
      ('4',''),
      ('4.1','4'),
      ('4.1.1','4.1'),
      ('4.1.2','4.1')]
content = {}
def rec(table, parent=None):
    while True:
        try:
            _code = table[0][0]
            _parent = table [0][1]
            if _parent == '':
                content[_code] = _parent
                return rec(table[1:])
            else:
                if _parent in content:
                    if content[_parent] == '':
                        content[_parent] = table[0]
                    else:
                        content[_parent] = content[_parent], table[0]
                    return rec(table[1:], parent=_parent)
                else:
                    content[_parent] = table[0]
                    return rec(table[1:], parent=_parent)           
        except IndexError:
            break
    return content

print(rec(table))

The output I'm getting:

{'1': ('1.1', '1'), '2': ('2.1', '2'), '2.1': ('2.1.1', '2.1'), '3':('3.1', '3'), '4': ('4.1', '4'), '4.1': (('4.1.1', '4.1'), ('4.1.2','4.1'))}

But the desired output would be:

{'1': ('1.1', '1'), '2': ('2.1', '2'), {'2.1': ('2.1.1', '2.1')}, '3': ('3.1','3'), '4': ('4.1', '4'), {'4.1': ('4.1.1', '4.1'), ('4.1.2', '4.1')}

I need something like:

{'node_id': '1', 'name':'somename', 'children': [{'node_id': '1.1' ,'name':'somename', 'children': [{'node_id': '1.1.1', 'name':'somename', 'children': [{'node_id': '1.1.1.1', 'name':'somename', 'children': []}]}, {'node_id': '1.1.2', 'name':'somename', 'children': []}, {'node_id': '1.1.3', 'name':'somename', 'children': []}]}, {'node_id': '1.2', 'name':'somename', 'children': []}]}

Any thoughts on how to achieve what I'm aiming for?

Alain T. · Accepted Answer · 2020-03-15 18:18:39Z

For your output to be a tree of nested dictionaries, it will need to have a regular structure where every node is a dictionary with values representing a dictionary of children down to the leaf nodes which would have an empty dictionary for their children.

Here's a simple loop that will build the tree:

table = [('1', ''),
      ('1.1', '1'),
      ('2', ''),
      ('2.1','2'),
      ('2.1.1','2.1'),
      ('3',''),
      ('3.1','3'),
      ('4',''),
      ('4.1','4'),
      ('4.1.1','4.1'),
      ('4.1.2','4.1')]

tree = { node:dict() for link in table for node in link }
for child,parent in table:
    tree[parent].update({child:tree[child]})

output:

print(tree[""])  # "" is te root

{
 '1': { '1.1': {}},
 '2': {
        '2.1': { '2.1.1': {}}
      },
 '3': { '3.1': {}},
 '4': {
        '4.1': {
                 '4.1.1': {},
                 '4.1.2': {}
               }
      }
}

as a side benefit, this structure gives you an index for all the nodes in the tree

With dictionaries of attributes (one of which is the list of children), the same approach can be used:

tree = { node:{"id":node,"children":[]} for link in table for node in link }
for child,parent in table:
    tree[parent]["children"].append(tree[child])

output:

print(tree[""]["children"]) # children of root

[ { 'id': '1',
    'children': [ { 'id': '1.1', 'children': []} ]
  },
  { 'id': '2',
    'children': [
                  { 'id': '2.1',
                    'children': [ {'id': '2.1.1', 'children': []} ]
                  } 
                ]
  },
  { 'id': '3',
    'children': [ { 'id': '3.1','children': []} ]
  },
  { 'id': '4',
    'children': [
                  { 'id': '4.1',
                    'children': [
                                  { 'id': '4.1.1', 'children': []},
                                  { 'id': '4.1.2', 'children': []}
                                ]
                  }
                ]
  }
]

A recursive approach is nice but would preform much slower and will not produce an index to access the nodes by their Id's:

def tree(links,node=""):
    return {"id":node, "children":[tree(links,child) for child,parent in links if parent==node] }

root = tree(table)

Thank you for the help, your answer helped me learn some more about dicts!

Ajax1234 · Accepted Answer · 2020-03-15 16:56:58Z

1

You can use recursion:

table = [('1', ''), ('1.1', '1'), ('2', ''), ('2.1', '2'), ('2.1.1', '2.1'), ('3', ''), ('3.1', '3'), ('4', ''), ('4.1', '4'), ('4.1.1', '4.1'), ('4.1.2', '4.1')]
def to_dict(d):
  return {'node_id':d, 'children':[*map(to_dict, [a for a, b in table if b == d])]}

result = [to_dict(a) for a, b in table if not b]

Output:

[{'node_id': '1', 'children': [{'node_id': '1.1', 'children': []}]}, {'node_id': '2', 'children': [{'node_id': '2.1', 'children': [{'node_id': '2.1.1', 'children': []}]}]}, {'node_id': '3', 'children': [{'node_id': '3.1', 'children': []}]}, {'node_id': '4', 'children': [{'node_id': '4.1', 'children': [{'node_id': '4.1.1', 'children': []}, {'node_id': '4.1.2', 'children': []}]}]}]

Edit: supposing your tuples in table have additional information:

table = [('1', '', 'someval0'), ('1.1', '1', 'someval1'), ('2', '', 'someval2'), ('2.1', '2', 'someval3'), ('2.1.1', '2.1', 'someval4'), ('3', '', 'someval5'), ('3.1', '3', 'someval6'), ('4', '', 'someval7'), ('4.1', '4', 'someval8'), ('4.1.1', '4.1', 'someval9'), ('4.1.2', '4.1', 'someval10')]
def to_dict(d):
  return {**(dict(zip(['node_id', 'name'], d))), 'children':[*map(to_dict, [(a, *c) for a, b, *c in table if b == d[0]])]}

result = [to_dict((a, *c)) for a, b, *c in table if not b]

Output:

[{'node_id': '1', 'name': 'someval0', 'children': [{'node_id': '1.1', 'name': 'someval1', 'children': []}]}, {'node_id': '2', 'name': 'someval2', 'children': [{'node_id': '2.1', 'name': 'someval3', 'children': [{'node_id': '2.1.1', 'name': 'someval4', 'children': []}]}]}, {'node_id': '3', 'name': 'someval5', 'children': [{'node_id': '3.1', 'name': 'someval6', 'children': []}]}, {'node_id': '4', 'name': 'someval7', 'children': [{'node_id': '4.1', 'name': 'someval8', 'children': [{'node_id': '4.1.1', 'name': 'someval9', 'children': []}, {'node_id': '4.1.2', 'name': 'someval10', 'children': []}]}]}]

edited Mar 15, 2020 at 16:56

answered Mar 15, 2020 at 16:23

Ajax1234

71.7k9 gold badges67 silver badges110 bronze badges

7 Comments

Matheus Baumgarten Over a year ago

Could you explain what's happening in there? The *map() part

Ajax1234 Over a year ago

@MatheusBaumgarten map applies the function to_dict to every element in the list resulting from the comprehension [a for a, b in table if b == d]. The * unpacks the iterator object returned by map into a list.

Matheus Baumgarten Over a year ago

What if i have more content on the tuples? Like (code,parent,name,morestuff)

Ajax1234 Over a year ago

@MatheusBaumgarten Can you clarify how that would change your current desired output?

Matheus Baumgarten Over a year ago

I want to create a treeview in kivy but instead of only displaying the code i want to display more content too

|

Collectives™ on Stack Overflow

Python recursion to sort list of tuples into tree structure

2 Answers 2

1 Comment

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related