Convert list of dictionaries into a nested dictionary

Question

I have a list of dictionaries that I got from the database in parent-child relationship:

data = [
  {"id":1, "parent_id": 0, "name": "Wood", "price": 0}, 
  {"id":2, "parent_id": 1, "name": "Mango", "price": 18}, 
  {"id":3, "parent_id": 2, "name": "Table", "price": 342}, 
  {"id":4, "parent_id": 2, "name": "Box", "price": 340}, 
  {"id":5, "parent_id": 4, "name": "Pencil", "price": 240}, 
  {"id":6, "parent_id": 0, "name": "Electronic", "price": 20}, 
  {"id":7, "parent_id": 6, "name": "TV", "price": 350}, 
  {"id":8, "parent_id": 6, "name": "Mobile", "price": 300}, 
  {"id":9, "parent_id": 8, "name": "Iphone", "price": 0}, 
  {"id":10, "parent_id": 9, "name": "Iphone 10", "price": 400}
]

I want to convert it to a nested dictionary such as

[ { "id": 1, "parent_id": 0, "name": "Wood", "price": 0, "children": [ { "id": 2, "parent_id": 1, "name": "Mango", "price": 18, "children": [ { "id": 3, "parent_id": 2, "name": "Table", "price": 342 }, { "id": 4, "parent_id": 2, "name": "Box", "price": 340, "children": [ { "id": 5, "parent_id": 4, "name": "Pencil", "price": 240 } ] } ] } ] }, { "id": 6, "parent_id": 0, "name": "Electronic", "price": 20, "children": [ { "id": 7, "parent_id": 6, "name": "TV", "price": 350 }, { "id": 8, "parent_id": 6, "name": "Mobile", "price": 300, "children": [ { "id": 9, "parent_id": 8, "name": "Iphone", "price": 0, "children": [ { "id": 10, "parent_id": 9, "name": "Iphone 10", "price": 400 } ] } ] } ] } ]

https://stackoverflow.com/questions/31643568/python-create-a-nested-dictionary-from-a-list-of-parent-child-values — Manoj Ravi, Oct 18 '19 at 04:46

score 1 · Answer 1 · answered Oct 18 '19 at 06:02

You can do this recursively, starting from the root nodes (where parent_id = 0) going downwards. But before your recursive calls, you can group nodes by their parent_id so that accessing them in each recursive call can be done in constant time:

levels = {}
for n in data:
    levels.setdefault(n['parent_id'], []).append(n)

def build_tree(parent_id=0):
    nodes = [dict(n) for n in levels.get(parent_id, [])]
    for n in nodes:
        children = build_tree(n['id'])
        if children: n['children'] = children
    return nodes

tree = build_tree()
print(tree)

Output

[{'id': 1, 'parent_id': 0, 'name': 'Wood', 'price': 0, 'children': [{'id': 2, 'parent_id': 1, 'name': 'Mango', 'price': 18, 'children': [{'id': 3, 'parent_id': 2, 'name': 'Table', 'price': 342}, {'id': 4, 'parent_id': 2, 'name': 'Box', 'price': 340, 'children': [{'id': 5, 'parent_id': 4, 'name': 'Pencil', 'price': 240}]}]}]}, {'id': 6, 'parent_id': 0, 'name': 'Electronic', 'price': 20, 'children': [{'id': 7, 'parent_id': 6, 'name': 'TV', 'price': 350}, {'id': 8, 'parent_id': 6, 'name': 'Mobile', 'price': 300, 'children': [{'id': 9, 'parent_id': 8, 'name': 'Iphone', 'price': 0,'children': [{'id': 10, 'parent_id': 9, 'name': 'Iphone 10', 'price': 400}]}]}]}]

score 0 · Answer 2 · answered Oct 18 '19 at 05:16

Code is documented inline. Ignoring the corner cases like circular relations etc.

# Actual Data
data = [
  {"id":1, "parent_id": 0, "name": "Wood", "price": 0}, 
  {"id":2, "parent_id": 1, "name": "Mango", "price": 18}, 
  {"id":3, "parent_id": 2, "name": "Table", "price": 342}, 
  {"id":4, "parent_id": 2, "name": "Box", "price": 340}, 
  {"id":5, "parent_id": 4, "name": "Pencil", "price": 240}, 
  {"id":6, "parent_id": 0, "name": "Electronic", "price": 20}, 
  {"id":7, "parent_id": 6, "name": "TV", "price": 350}, 
  {"id":8, "parent_id": 6, "name": "Mobile", "price": 300}, 
  {"id":9, "parent_id": 8, "name": "Iphone", "price": 0}, 
  {"id":10, "parent_id": 9, "name": "Iphone 10", "price": 400}
]

# Create Parent -> child links using dictonary
data_dict = { r['id'] : r for r in data}
for r in data:
    if r['parent_id'] in data_dict:
        parent = data_dict[r['parent_id']]
        if 'children' not in parent:
            parent['children'] = []
        parent['children'].append(r)

# Helper function to get all the id's associated with a parent
def get_all_ids(r):
    l = list()
    l.append(r['id'])
    if 'children' in r:
        for c in r['children']:
            l.extend(get_all_ids(c))
    return l

# Trimp the results to have a id only once
ids = set(data_dict.keys())
result = []
for r in data_dict.values():
    the_ids = set(get_all_ids(r))
    if ids.intersection(the_ids):
        ids = ids.difference(the_ids)
        result.append(r)
print (result)

Output:

[{'id': 1, 'parent_id': 0, 'name': 'Wood', 'price': 0, 'children': [{'id': 2, 'parent_id': 1, 'name': 'Mango', 'price': 18, 'children': [{'id': 3, 'parent_id': 2, 'name': 'Table', 'price': 342}, {'id': 4, 'parent_id': 2, 'name': 'Box', 'price': 340, 'children': [{'id': 5, 'parent_id': 4, 'name': 'Pencil', 'price': 240}]}]}]}, {'id': 6, 'parent_id': 0, 'name': 'Electronic', 'price': 20, 'children': [{'id': 7, 'parent_id': 6, 'name': 'TV', 'price': 350}, {'id': 8, 'parent_id': 6, 'name': 'Mobile', 'price': 300, 'children': [{'id': 9, 'parent_id': 8, 'name': 'Iphone', 'price': 0, 'children': [{'id': 10, 'parent_id': 9, 'name': 'Iphone 10', 'price': 400}]}]}]}]

aelmosalamy · Answer 3 · 2019-10-18T05:34:49.360

I worked out a VERY SHORT solution, I believe it isn't the most efficient algorithm, but it does the job, will need a hell of optimization to work on very large data sets.

for i in range(len(data)-1, -1, -1):
    data[i]["children"] = [child for child in data if child["parent_id"] == data[i]["id"]]
        for child in data[i]["children"]:
                data.remove(child)

Here is the complete explanation:

data = [
  {"id":1, "parent_id": 0, "name": "Wood", "price": 0}, 
  {"id":2, "parent_id": 1, "name": "Mango", "price": 18}, 
  {"id":3, "parent_id": 2, "name": "Table", "price": 342}, 
  {"id":4, "parent_id": 2, "name": "Box", "price": 340}, 
  {"id":5, "parent_id": 4, "name": "Pencil", "price": 240}, 
  {"id":6, "parent_id": 0, "name": "Electronic", "price": 20}, 
  {"id":7, "parent_id": 6, "name": "TV", "price": 350}, 
  {"id":8, "parent_id": 6, "name": "Mobile", "price": 300}, 
  {"id":9, "parent_id": 8, "name": "Iphone", "price": 0}, 
  {"id":10, "parent_id": 9, "name": "Iphone 10", "price": 400}
]

# Looping backwards,placing the lowest child
# into the next parent in the heirarchy
for i in range(len(data)-1, -1, -1):
    # Create a dict key for the current parent in the loop called "children"
    # and assign to it a list comprehension that loops over all items in the data
    # to get the elements which have a parent_id equivalent to our current element's id
    data[i]["children"] = [child for child in data if child["parent_id"] == data[i]["id"]]
    # since the child is placed inside our its parent already, we will
    # remove it from its actual position in the data
    for child in data[i]["children"]:
        data.remove(child)
# print the new data structure      
print(data)

And here is the output:

[{'id': 1, 'parent_id': 0, 'name': 'Wood', 'price': 0, 'children': [{'id': 2, 'parent_id': 1, 'name': 'Mango', 'price': 18, 'children': [{'id': 3, 'parent_id': 2, 'name': 'Table', 'price': 342, 'children': []}, {'id': 4, 'parent_id': 2, 'name': 'Box', 'price': 340, 'children': [{'id': 5, 'parent_id': 4, 'name': 'Pencil', 'price': 240, 'children': []}]}]}]}, {'id': 6, 'parent_id': 0, 'name': 'Electronic', 'price': 20, 'children': [{'id': 7, 'parent_id': 6, 'name': 'TV', 'price': 350, 'children': []}, {'id': 8, 'parent_id': 6, 'name': 'Mobile', 'price': 300, 'children': [{'id': 9, 'parent_id': 8, 'name': 'Iphone', 'price': 0, 'children': [{'id': 10, 'parent_id': 9, 'name': 'Iphone 10', 'price': 400, 'children': []}]}]}]}]

Convert list of dictionaries into a nested dictionary

3 Answers3