Convert flattened dictionary to nested dictionary

Question

This is my flattened dictionary:

d={"QR": "", "Customer Details": "",
 "feature prompt": "something", "chain": "lee", "store": "levis"}

I want output as a nested dictionary; each empty string value represents the beginning of a new dictionary. Desired output:

{
    "QR": {
        "Customer Details": {
            "feature prompt": "something",
            "chain": "lee",
            "store": "levis"
        }
    }
}

My code:

d={"QR": "", "Customer Details": "",
 "feature prompt": "something", "chain": "lee", "store": "levis"}

def nest_dict(d):
    result={}
    for k,v in d.items():
        split(k,v,result)
        #print(k)
        #print(v)
    return result

def split(k,v,out):
    if v=='':
        split(k,v,out.setdefault(k,{}))
    else:
        out[k]=v

nest_dict(d)

However, this gives me a RecursionError:

Traceback (most recent call last):
  File "/Users/asmita/so_test/test.py", line 18, in <module>
    print(nest_dict(d))
  File "/Users/asmita/so_test/test.py", line 7, in nest_dict
    split(k,v,result)
  File "/Users/asmita/so_test/test.py", line 14, in split
    split(k,v,out.setdefault(k,{}))
  File "/Users/asmita/so_test/test.py", line 14, in split
    split(k,v,out.setdefault(k,{}))
  File "/Users/asmita/so_test/test.py", line 14, in split
    split(k,v,out.setdefault(k,{}))
  [Previous line repeated 994 more times]
  File "/Users/asmita/so_test/test.py", line 13, in split
    if v=='':
RecursionError: maximum recursion depth exceeded in comparison

What if a later value is also an empty string: will the entire rest of the dictionary be the value of that key? Are there only ever single dictionary values in your flattened dictionary? Or do you have examples of what the data would look like for a more complex dictionary? — Grismar, Jan 06 '23 at 09:56
Hi Asmita, welcome to SO. Can you add mroe details to your question? How do you want this transformation to take place? Are the empty strings in values responsible for the nesting process? — Akshay Sehgal, Jan 06 '23 at 09:56
Do you always want `QR -> customer details -> rest of the keys` as your nesting or it works based on the sequence of keys with empty string values `' '`. Also do explain what happens if one of the other keys is empty? for example `{'QR': '', 'Customer Details': '', 'feature prompt': 'something', 'chain': ' ', 'store': 'levis'}` — Akshay Sehgal, Jan 06 '23 at 10:11
Hi akshay.....thanks for your reply....I want my output as:{ "QR": { "Customer Details": { "feature prompt": "something", "chain": "lee", "store": "levis" } } } when the key value of dictionary is empty string we should take that key as first dictionary...these process will continue.... — coder, Jan 06 '23 at 10:11
hi, thanks, that you have already clarified in the question. what everyone is asking is how does that transformation take place? Please read the comments by @Grismar and me — Akshay Sehgal, Jan 06 '23 at 10:13
hi..transformation is on the basis of empty string only....I had just given you small portion if it works den entire dictionary also works...I hope u got my pont..if u need further clarification please connect with me — coder, Jan 06 '23 at 10:23

CrazyChucky · Accepted Answer · 2023-01-06T23:31:49.640

Iterative Solution

Your split method calls itself in an infinite loop, which causes the RecursionError. You don't really need recursion at all for this. Just keep a reference to the current "layer", and reassign it each time you need to add a new dictionary.

d = {
    'QR': '',
    'Customer Details': '',
    'feature prompt': 'something',
    'chain': 'lee',
    'store': 'levis',
}

def nest_dict(flat_dict):
    current_level = result = {}

    for key, value in flat_dict.items():
        if value:
            current_level[key] = value
        else:
            current_level[key] = {}
            current_level = current_level[key]

    return result

print(nest_dict(d))

Output:

{'QR': {'Customer Details': {'feature prompt': 'something', 'chain': 'lee', 'store': 'levis'}}}

Recursive Solution

If you definitely want to use recursion, you probably want your main function to call itself, rather than delegating to a second function that does so. In this implementation, when you come across a blank value, the function calls itself, giving the subcall a version of the dictionary with the current key removed (then breaks its loop, so it doesn't double-process every subsequent key).

def nest_dict(flat_dict):
    result = {}

    for key, value in flat_dict.items():
        if value:
            result[key] = value
        else:
            result[key] = nest_dict(
                {k:v for k, v in flat_dict.items() if k != key}
            )
            break

    return result

A Word of Caution

There are two main pitfalls with recursive programming:

It can be tricky to wrap your head around and correctly implement, especially for beginners at programming.
Python, under the hood, is not really optimized for recursion, and iterating too many layers deep will, as you've seen, result in a RecursionError (to prevent a stack overflow).

The second issue is unlikely to be a factor here unless your dictionaries are truly enormous; the recursion limit is usually set to 1,000. For the first, your mileage may vary. If nothing else, it can be fun to experiment with!

Convert flattened dictionary to nested dictionary

1 Answers1

Iterative Solution

Recursive Solution

A Word of Caution

Linked