Python: Merge list of nested dictionary and get a dictionary (tree)

Question

I have a following list of "dict" for example :

List1= [{'Europe': {'DE': {'Berlin': ['jack']}}},
        {'Europe': {'DE': {'KL': ['Paul']}}},
        {'Europe': {'FR': {'Paris': ['Jean', "Pierre"]}}}]

and I would like to transform it with Python into a dictionary having the tree structure like :

output = {"Europe": { "DE": { "KL":     ["Paul"],
                              "Berlin": ["Jack"]
                             },
                       "FR" : { "Paris": ["Jean", "Pierre"]}
                     }
          }

Can you help me ? my function get the list1 and return the output dict ?
Thank you

This is a trivial data manipulation problem. What have you tried? Please include your effort. — DYZ, Aug 04 '21 at 23:55
What happened when you tried to write code to solve the problem? You are expected to make your own attempt first here. Please see https://meta.stackoverflow.com/questions/261592/how-much-research-effort-is-expected-of-stack-overflow-users . — Karl Knechtel, Aug 05 '21 at 01:34

Niel Godfrey Pablo Ponciano · Answer 1 · 2021-08-05T01:43:40.957

Here is a simple recursive solution. This solution is generic enough to be able to support any future changes in the structure of your dictionary, you can even use this for purposes other than this list of countries. By taking advantage of the mutability property of dict and list, we can pass it around each recursive call and perform:

If the element in lhs (left-hand side, here is List1) doesn't appear yet in the rhs (right-hand side, here is result), copy it as is.
If the element in lhs already appears in rhs, do a recursive call to merge the inner elements.
If the value in lhs is a list, add it to the rhs.

import copy
import json

List1= [
    {'Europe': {'DE': {'Berlin': ['Jack']}}},
    {'Europe': {'DE': {'KL': ['Paul']}}},
    {'Asia': {'PH': {'Manila': ['Jose', 'Rizal']}}},
    {'Europe': {'FR': {'Paris': ['Jean', "Pierre"]}}},
    {'Asia': {'PH': {'Manila': ['Andres']}}},
    {'Asia': {'KH': {'Siem Reap': ['Angkor']}}},
    {'Europe': {'DE': {'Berlin': ['Jill']}}},
    {'Asia': {'PH': {'Cebu': ['Lapulapu']}}},
    {'Asia': {'PH': {'Manila': ['Bonifacio']}}},
    {'Europe': {'ES': {'Valencia': ['Paella']}}},
    {'Asia': {'KH': {'Phnom Penh': ['Wat']}}},
    {'Europe': {'ES': {'Valencia': ['Me gusta mucho!']}}},
    {'Asia': {'PH': {'Palawan': ['Beach']}}},
    {'Asia': {'PH': {'Palawan': ['Cave']}}},
    {'Asia': {'PH': {'Palawan': []}}},
]

result = {}

def merge(lhs, rhs):
    if isinstance(lhs, dict):
        for key, value in lhs.items():
            if key not in rhs:
                rhs[key] = copy.deepcopy(value)  # Thanks to @sabik for the code review (see comments section). To avoid updating the source data List1, here we would perform a deep copy instead of just <rhs[key] = value>.
            else:
                merge(value, rhs[key])
    elif isinstance(lhs, list):
        rhs.extend(lhs)

for item in List1:
    merge(item, result)

print(json.dumps(result, indent=4))

Output:

{
    "Europe": {
        "DE": {
            "Berlin": [
                "Jack",
                "Jill"
            ],
            "KL": [
                "Paul"
            ]
        },
        "FR": {
            "Paris": [
                "Jean",
                "Pierre"
            ]
        },
        "ES": {
            "Valencia": [
                "Paella",
                "Me gusta mucho!"
            ]
        }
    },
    "Asia": {
        "PH": {
            "Manila": [
                "Jose",
                "Rizal",
                "Andres",
                "Bonifacio"
            ],
            "Cebu": [
                "Lapulapu"
            ],
            "Palawan": [
                "Beach",
                "Cave"
            ]
        },
        "KH": {
            "Siem Reap": [
                "Angkor"
            ],
            "Phnom Penh": [
                "Wat"
            ]
        }
    }
}

I think this will modify some parts of the source items; if that's a problem, the `merge` function will need to create a new list or dict rather than using `rhs[key] = value` when `value` is a list or a dict — Jiří Baum, Aug 05 '21 at 01:38
Indeed! Thank you @sabik for the code review and catching this unwanted side-effect. I updated the code to perform a deep copy of `List1` first via `rhs[key] = copy.deepcopy(value)`. — Niel Godfrey Pablo Ponciano, Aug 05 '21 at 01:46
Another way would be to initialise it to `[]` or `{}` (as appropriate) and then do the recursion; either way works — Jiří Baum, Aug 05 '21 at 03:03

score 1 · Answer 2 · answered Aug 05 '21 at 00:23

This works, although I feel like there is probably a more elegant way of doing it.

all_country_codes = set([list(x['Europe'].keys())[0] for x in List1])
output = []
for code in all_country_codes:
    results = [x['Europe'][code] for x in List1 if code in x['Europe'].keys()]
    country_code_dict = {}
    for country_dictionary in results:
        country_code_dict.update(country_dictionary)
    output.append({code: country_code_dict})

almost_there_dict = {}
for reformatted_dict in output:
    almost_there_dict.update(reformatted_dict)

final_dict = {}
final_dict['Europe'] = almost_there_dict

fitz · Accepted Answer · 2021-08-05T07:47:20.150

I think you can use nested defaultdict to do it. Here is the solution, it inspired by Nested defaultdict of defaultdict

import json
from collections import defaultdict

# List1 = [{'Europe': {'DE': {'Berlin': ['jack']}}},
#      {'Europe': {'DE': {'KL': ['Paul']}}},
#      {'Europe': {'FR': {'Paris': ['Jean', "Pierre"]}}}]

List1 = [{'Europe': {'DE': {'Berlin': {'a': ['jack']}}}},
         {'Europe': {'DE': {'Berlin': {'b': {'b1': ['xxx']}}}}}, 
         {'Europe': {'FR': {'Paris': ['Jean', "Pierre"]}}}]

def create_tree():
    return defaultdict(create_tree)

def set_node(i, node, k):
    if isinstance(i, dict):
        for k, v in i.items():
            if isinstance(v, list):
                node[k] = v
            else:
                node = node[k]
                set_node(v, node, k)
                                
def get_tree():
    tree = create_tree()
    for d in List1:
        set_node(d, tree, None)
    return tree

tree = get_tree()
# if you want to get the dict of tree, use:json.loads(json.dumps(tree))
print(json.dumps(tree, indent=4))

Thank you it is exactly what I needed especially because my input is more complex than the example I put in the question . — Remus 007, Aug 05 '21 at 13:50
My pleasure.In fact, Niel Godfrey Ponciano's method can also achieve this, and it is worth understanding. — fitz, Aug 05 '21 at 14:51

score 0 · Answer 4 · answered Aug 05 '21 at 04:32

If the depth of your nested dict does not change, you can just try looping and use setdefault and update if a key is found:-

List1= [{'Europe': {'DE': {'Berlin': ['Jack']}}},
        {'Europe': {'DE': {'KL': ['Paul']}}},
        {'Europe': {'FR': {'Paris': ['Jean', "Pierre"]}}}]

output = {}
for l in List1:
    
    for k,v in l.items():
        #outer key
        output.setdefault(k, {})
        
        for key,val in v.items():
            #inner key
            output[k].setdefault(key, {})
            #update inner key
            output[k][key].update(val)

which returns (keep in mind depending on your Python version, dict might be sorted or not):

{'Europe': {'DE': {'Berlin': ['Jack'], 'KL': ['Paul']},
  'FR': {'Paris': ['Jean', 'Pierre']}}}

Python: Merge list of nested dictionary and get a dictionary (tree)

4 Answers4