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 does not require recursion.</p>

<p>First create a dictionary of nodes, one for each item using <code>id</code> 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 <code>None</code>).  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.</p>

<p>The roots of the forrest are the nodes that have <code>None</code> for a parent.</p>

python dictionary recursion parent-child