python - Convert list of dicts to hierarchy/multiple nested dicts - issue with orders
<p>Currently I have these input:</p>

<pre><code>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}]
</code></pre>

<p>This is my recursive function:</p>

<pre><code>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
</code></pre>

<p>This is my main code:</p>

<pre><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
</code></pre>

<p>So, with above given data and the code, I have the result as below:</p>

<pre><code>[{
        '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
            }
        ]
    }
]
</code></pre>

<p>This result is as you could see missing the items with <code>id = 4</code> and <code>id = 5</code> because during the loops, the parents of these items haven't been created yet (the items with <code>id = 5</code> &amp; <code>id = 6</code>). 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. </p>

<p><strong><em>UPDATED</em></strong></p>

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

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

<pre><code>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
</code></pre>

<p><strong><em>UPDATED-2</em></strong></p>

<p>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!</p>

<pre><code>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
</code></pre>

<p>This would be my solution:</p>

<pre><code>#! /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)
</code></pre>

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

<pre><code>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}
</code></pre>

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

python dictionary recursion parent-child