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?

Answer 1

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)

Answer 2

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': []}]}]}]