Python | Convert nested dictionary into flattened dictionary

Given a nested dictionary, the task is to convert this dictionary into a flattened dictionary where the key is separated by ‘_’ in case of the nested key to be started.

Method #1: Using Naive Approach 

Step-by-step approach :

1. The function checks if the input dd is a dictionary. If it is, then it iterates over each key-value pair in the dictionary, and calls the flatten_dict function recursively on the value of each key. It concatenates the original key and the returned key from the recursive call with the separator, and uses that as the new key in the flattened dictionary. It sets the value of the new key to the returned value from the recursive call.
2. If the input dd is not a dictionary, the function creates a new dictionary with a single key-value pair, where the key is the prefix argument (which is the path to the current value in the original nested dictionary), and the value is the input dd itself.
3. The code then initializes a nested dictionary ini_dict with some sample data.
4. The code prints the initial dictionary ini_dict.
5. The code calls the flatten_dict function on the ini_dict dictionary and prints the resulting flattened dictionary.

Time complexity: O(n^2), where n is the total number of keys in the nested dictionary.
Auxiliary space: O(n), where n is the total number of keys in the nested dictionary. The auxiliary space is used to store the result of the flatten dictionary in the form of a new dictionary.

Method #2: Using mutableMapping 

Time Complexity: O(n)
Auxiliary Space: O(n)

Method #3: Using Python Generators  

Time complexity: O(n), where n is the total number of keys in the nested dictionary
Auxiliary space: O(n), where n is the total number of keys in the nested dictionary. 

Method #4: Using recursion and a separator

1. Define a function “flatten_dict” that takes in three parameters: dd (a dictionary), separator (a string, default value “_”), and prefix (a string, default value “”).
2. Initialize an empty dictionary “res”.
3. Iterate through each key-value pair in the dictionary “dd”.
4. Check if the value associated with the current key is itself a dictionary or not. If it is a dictionary, then recursively call the “flatten_dict” function with the value as the new dictionary to be flattened, the separator and prefix updated with the current key and separator value.
5. If the value is not a dictionary, then add the key-value pair to the “res” dictionary, where the key is the concatenation of prefix, separator and current key.
6. Return the final “res” dictionary.

initial dictionary {'Lazyroar': {'Geeks': {'for': 7}}, 'for': {'Lazyroar': {'Geeks': 3}}, 'Geeks': {'for': {'for': 1, 'Lazyroar': 4}}}
final dictionary {'Lazyroar_Geeks_for': 7, 'for_Lazyroar_Geeks': 3, 'Geeks_for_for': 1, 'Geeks_for_Lazyroar': 4}

The time complexity of this algorithm is O(N), where N is the total number of keys in the nested dictionary. This is because the algorithm iterates through each key exactly once.
The space complexity is also O(N), where N is the total number of keys, since the algorithm creates a new dictionary “res” to store the flattened dictionary.

Method 5: Using a stack data structure

The idea is to iterate through the dictionary and push all nested dictionaries into a stack. Then, we can pop each dictionary from the stack, iterate through its key-value pairs, and append the key-value pairs to a flattened dictionary.

1. Initialize an empty stack.
2. Push the initial dictionary onto the stack.
3. Initialize an empty flattened dictionary.
4. While the stack is not empty, do the following:
   a. Pop the top dictionary from the stack.
   b. For each key-value pair in the popped dictionary, do the following:
   i. If the value is a dictionary, push it onto the stack with its key as the prefix.
   ii. Otherwise, add the key-value pair to the flattened dictionary with the prefix and separator (default is ‘_’).
5. Return the flattened dictionary.

initial_dictionary {'Lazyroar': {'Geeks': {'for': 7}}, 'for': {'Lazyroar': {'Geeks': 3}}, 'Geeks': {'for': {'for': 1, 'Lazyroar': 4}}}
final_dictionary {'Geeks_for_for': 1, 'Geeks_for_Lazyroar': 4, 'for_Lazyroar_Geeks': 3, 'Lazyroar_Geeks_for': 7}

Time complexity: O(n), where n is the total number of key-value pairs in the input nested dictionary.
Auxiliary space: O(n), where n is the total number of key-value pairs in the input nested dictionary.

Method 6: Using a recursive function without a separator

Here is an alternative method that uses a recursive function without a separator. It works by iterating over the items of the dictionary and checking whether each value is another dictionary. If it is, the function calls itself recursively and concatenates the key with the new keys returned by the recursive call. If it is not, the function simply adds the key-value pair to the result dictionary.

Here’s the step by step approach:

1. Define a function called flatten_dict_recursive that takes a dictionary d as input.
2. Initialize an empty dictionary called result.
3. For each key-value pair in d, do the following:
   a. If the value is a dictionary, call flatten_dict_recursive with the value and concatenate the returned keys with the current key.
   b. If the value is not a dictionary, add the current key and value to result.
4. Return result.

initial_dictionary {'Lazyroar': {'Geeks': {'for': 7}}, 'for': {'Lazyroar': {'Geeks': 3}}, 'Geeks': {'for': {'for': 1, 'Lazyroar': 4}}}
final_dictionary {'Geeksforfor': 1, 'GeeksforLazyroar': 4, 'forLazyroarGeeks': 3, 'LazyroarGeeksfor': 7}

Time complexity: The time complexity of this function is O(n), where n is the total number of key-value pairs in the dictionary. 

Auxiliary space: The auxiliary space complexity of this function is O(n), where n is the total number of key-value pairs in the dictionary.