python - Convert list of dicts to hierarchy/multiple nested dicts - issue with orders

Question

Currently I have these input:

query = [{'id': 1, 'desc': 'desc_father', 'parent_id': None}
         ,{'id': 2, 'desc': 'desc_child_1', 'parent_id': 10}
         ,{'id': 3, 'desc': 'desc_child_2', 'parent_id': 2}
         ,{'id': 4, 'desc': 'desc_child_5', 'parent_id': 5}
         ,{'id': 5, 'desc': 'desc_child_6', 'parent_id': 6}
         ,{'id': 6, 'desc': 'desc_child_1', 'parent_id': 1}]

This is my recursive function:

def recursive(parent_list, child_dict, parent_id):
    for l in parent_list:
        if parent_id in l.values():
            if 'children' not in l:
                l['children'] = []
            l['children'].append(child_dict)
            break
        else:
            for i in l:
                if isinstance(l[i], list):
                    recursive(d[i], child_dict, parent_id)
    return parent_list

This is my main code:

results = []
for q in query:
    dict_item = {}
    dict_item['id'] = q['id']
    dict_item['desc'] = q['desc']
    if q['parent_id'] is None:
        results.append(dict_item)
    else:
        results= recursive(results, dict_item, q['parent_id'])
return results

So, with above given data and the code, I have the result as below:

[{
        'desc' : 'desc_father',
        'id' : 1,
        'children' : [{
                'desc' : 'desc_child_1',
                'id' : 2,
                'children' : [{
                        'desc' : 'desc_child_2',
                        'id' : 3
                    }
                ]
            }, {
                'desc' : 'desc_child_1',
                'id' : 6
            }
        ]
    }
]

This result is as you could see missing the items with id = 4 and id = 5 because during the loops, the parents of these items haven't been created yet (the items with id = 5 & id = 6). I am having difficulties in fixing this problem as I don't know how to traverse back or forward the list to create the father item before the children ones. Help is appreciated. Thanks in advance.

UPDATED

I have added in one case for my query, which is the item with id = 2, this time the item is updated its parent_id to 10 (parent_id = 10), since we do not have the item with id = 10 as parent in our return result, so this id = 2 item will also be a root.

My new code based on Scott Hunter guidance but I still could not make it to work. I must have misunderstood somewhere:

new_dict = {}
for q in query:
    q['Children'] = []
    new_dict[q['id']] = q

for k, v in new_dict.iteritems():
    print k, v
    if v['parent_id'] is not None and v['parent_id'] in new_dict:
        new_dict[k]['Children'].append(v)

print new_dict

UPDATED-2

Now I make it to work, based on Scott Hunter suggestion, please see my below code. However the code looks ugly with too many for, is there anyway that I could perfect this? Thanks a lot for your support, just one more step and it will be done!

new_dict = {}

for q in query:
    q['children'] = []
    q['parent'] = 1
    new_dict[q['id']] = q

for k, v in new_dict.iteritems():
    p_id = v['parent_id']
    for kk, vv in new_dict.iteritems():
        if kk == p_id:
            v['parent'] = 0
            vv['children'].append(v)

results = []

for d_id, d_item in new_dict.iteritems():
    if d_item['parent'] == 1:
        results.append(d_item)

print results

Answer 1

This would be my solution:

#! /usr/bin/env python3
from pprint import pprint
query = [{'id': 1, 'desc': 'desc_father', 'parent_id': None}
         ,{'id': 2, 'desc': 'desc_child_1', 'parent_id': 1}
         ,{'id': 3, 'desc': 'desc_child_2', 'parent_id': 2}
         ,{'id': 4, 'desc': 'desc_child_5', 'parent_id': 5}
         ,{'id': 5, 'desc': 'desc_child_6', 'parent_id': 6}
         ,{'id': 6, 'desc': 'desc_child_1', 'parent_id': 1}]


def rec(query, parent):
    parent['children'] = []
    for item in query:
        if item['parent_id'] == parent['id']:
            parent['children'].append(item)
            rec(query, item)


root = {'id': None}
rec(query, root)

pprint(root, indent=4)

It gives me the output (The keys are out of order, but that's what you get when you use a dictionary)

maurice@ubuntu:~/Dev/random$ python recursion_tree.py 
{   'children': [   {   'children': [   {   'children': [],
                                            'desc': 'desc_child_2',
                                            'id': 3,
                                            'parent_id': 2}],
                        'desc': 'desc_child_1',
                        'id': 2,
                        'parent_id': 1},
                    {   'children': [   {   'children': [   {   'children': [   ],
                                                                'desc': 'desc_child_5',
                                                                'id': 4,
                                                                'parent_id': 5}],
                                            'desc': 'desc_child_6',
                                            'id': 5,
                                            'parent_id': 6}],
                        'desc': 'desc_child_1',
                        'id': 6,
                        'parent_id': 1}],
    'desc': 'desc_father',
    'id': 1,
    'parent_id': None}

This should even work with multiple root nodes (there will be a dummy Node with the id None at the top though)

Answer 2

This does not require recursion.

First create a dictionary of nodes, one for each item using id as the key, which includes an empty list of children. Then you can scan that dictionary, and add each node to the list of children for its parent (skipping those whose parent is None). Once this scan is complete, every node that isn't a root will be in the child list of its parent, and thus all trees will be complete.

The roots of the forrest are the nodes that have None for a parent.