Sometimes, while working with Python dictionaries, we can have a problem in which we need to extract all the keys of nested dictionaries and render them in sorted order. This kind of application can occur in domains in which we work with data. Lets discuss certain ways in which this task can be performed.
Method #1 : Using yield + isinstance() + loop The combination of above functions can be used to perform this task. In this, we perform the task of detection of keys using isinstance(). The yield keyword is used to add intermediate results.
Python3
# Python3 code to demonstrate working of # Sorted Nested Keys in Dictionary# Using yield + isinstance() + loopdef hlper_fnc(test_dict): for key, val in test_dict.items(): yield key if isinstance(val, dict): yield from val# initializing dictionarytest_dict = {'gfg': 43, 'is': {'best' : 14, 'for' : 35, 'neveropen' : 42}, 'and' : {'CS' : 29}}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# Sorted Nested Keys in Dictionary# Using yield + isinstance() + loopres = sorted(hlper_fnc(test_dict)) # printing result print("The sorted nested keys : " + str(res)) |
The original dictionary is : {‘and’: {‘CS’: 29}, ‘gfg’: 43, ‘is’: {‘for’: 35, ‘best’: 14, ‘neveropen’: 42}} The sorted nested keys : [‘CS’, ‘and’, ‘best’, ‘for’, ‘neveropen’, ‘gfg’, ‘is’]
Time Complexity: O(n), where n is the length of the list test_list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list
Method #2 : Using sorted() + list comprehension + isinstance() The combination of above functions offer a shorthand solution to this problem. In this, the sorting is done using sorted(). The isinstance() is used to detect keys.
Python3
# Python3 code to demonstrate working of # Sorted Nested Keys in Dictionary# Using sorted() + list comprehension + isinstance()# initializing dictionarytest_dict = {'gfg': 43, 'is': {'best' : 14, 'for' : 35, 'neveropen' : 42}, 'and' : {'CS' : 29}}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# Sorted Nested Keys in Dictionary# Using sorted() + list comprehension + isinstance()res = sorted([key for val in test_dict.values() if isinstance(val, dict) for key in val] + list(test_dict)) # printing result print("The sorted nested keys : " + str(res)) |
The original dictionary is : {‘and’: {‘CS’: 29}, ‘gfg’: 43, ‘is’: {‘for’: 35, ‘best’: 14, ‘neveropen’: 42}} The sorted nested keys : [‘CS’, ‘and’, ‘best’, ‘for’, ‘neveropen’, ‘gfg’, ‘is’]
Method 3 : use a recursive function
step-by-step approach:
Define a function, collect_keys, that takes a dictionary as input.
Inside the function, create an empty list to collect the keys.
Loop through each key-value pair in the dictionary.
If the value is a dictionary, call the collect_keys function recursively on the value and append the result to the list of keys.
Otherwise, append the key to the list of keys.
Sort the list of keys.
Return the list of keys.
Call the collect_keys function on the original dictionary.
Print the sorted list of keys.
Python3
# Python3 code to demonstrate working of # Sorted Nested Keys in Dictionary# Using recursive function to collect keys# initializing dictionarytest_dict = {'gfg': 43, 'is': {'best' : 14, 'for' : 35, 'neveropen' : 42}, 'and' : {'CS' : 29}}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# define function to collect keys recursivelydef collect_keys(dictionary): keys = [] for key, value in dictionary.items(): if isinstance(value, dict): keys += collect_keys(value) keys.append(key) keys.sort() return keys# call collect_keys on the original dictionaryres = collect_keys(test_dict)# printing result print("The sorted nested keys : " + str(res)) |
The original dictionary is : {'gfg': 43, 'is': {'best': 14, 'for': 35, 'neveropen': 42}, 'and': {'CS': 29}}
The sorted nested keys : ['CS', 'and', 'best', 'for', 'neveropen', 'gfg', 'is']
The time complexity of this approach is O(n log n) due to the sorting step, where n is the total number of keys in the dictionary (including nested keys).
The auxiliary space complexity is O(n) to store the list of keys.
