Python – Extract selective keys’ values Including Nested Keys

Sometimes, while working with Python dictionaries, we can have a problem in which we need to extract selective keys’ values. This problem has been solved earlier, but sometimes, we can have multiple nestings and certain keys may be present in inner records. This problem caters all the nestings for extraction of keys’ values. Let’s discuss certain way in which this task can be solved.

Input : 
test_dict = {‘gfg’: {‘Lazyroar’: {‘best’ : 3}}} 
key_list = [‘best’, ‘Lazyroar’] 
Output : {‘Lazyroar’: {‘best’: 3}, ‘best’: 3}

Input : 
test_dict = {‘gfg’: {‘geek’: {‘good’ : 3}}} 
key_list = [‘best’, ‘Lazyroar’] 
Output : {} 

Method 1: Using recursion + loop + yield 
The combination of above functionalities can be used to solve this problem. In this, we perform the task of checking for key using conditional statements and check for nestings using recursion. The yield operator is used to dynamically return the key for assignment as it occurs.

The original dictionary is : {'gfg': {'is': {'best': 3}}, 'for': {'all': 4}, 'Lazyroar': 5}
The extracted values : {'best': 3, 'Lazyroar': 5}

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

Method 2-uses recursion and a helper function:

we define a helper function _get_vals_helper that recursively traverses the dictionary and extracts the values corresponding to the keys in key_list. The function returns a dictionary containing the extracted values. We call this function from the main get_vals function and return its result.

The original dictionary is : {'gfg': {'is': {'best': 3}}, 'for': {'all': 4}, 'Lazyroar': 5}
The extracted values : {'gfg': {'is': {'best': 3}}, 'Lazyroar': 5}

Time complexity: O(N), where N is the total number of elements in the input dictionary.
Auxiliary space: O(N), where N is the total number of elements in the input dictionary. 

Method 3-Using recursion and a list comprehension.

• Initialize an empty list ‘result‘
• Loop through each item (key, value pair) in the ‘test_dict‘
  • If the current key is in the ‘key_list‘, append the (key, value) pair to the ‘result’ list.
  • If the current value is a dictionary, recursively call the ‘get_vals‘ function with the current value and ‘key_list’ and append the result to the ‘result‘ list.
• Convert the ‘result‘ list to a dictionary and return it.

The original dictionary is : {'gfg': {'is': {'best': 3}}, 'for': {'all': 4}, 'Lazyroar': 5}
The extracted values : {'Lazyroar': 5, 'best': 3}

Time Complexity: The time complexity of the function is O(n^2) where n is the number of elements in the input dictionary. This is because the function loops through each key-value pair in the dictionary and also recursively calls itself if a value is a dictionary. In the worst-case scenario, if all values are dictionaries, then the function will call itself n times for n elements in the dictionary, leading to a time complexity of O(n^2).

Auxiliary Space: The space complexity of the function is also O(n^2) in the worst-case scenario, where all values in the dictionary are dictionaries. This is because each recursive call creates a new list of (key, value) pairs to append to the ‘result’ list. Therefore, the space required for the ‘result’ list can grow up to O(n^2) with the increasing depth of recursion.

Method 4: Using a stack and iterative approach

Extracting values from a nested dictionary with given keys is by using a stack and an iterative approach.

Step-by-step approach:

• Create an empty dictionary result_dict to store the extracted values.
• Create an empty stack and push the given dictionary test_dict into it.
• While the stack is not empty:
  a. Pop the top item from the stack.
  b. If the popped item is a dictionary and contains any key from the key_list, extract the corresponding value and add it to result_dict.
  c. If the popped item is a dictionary and contains any other dictionary, push those dictionaries onto the stack.
• Return the result_dict.

Below is the implementation of the above approach:

{'Lazyroar': 5, 'best': 3}

Time complexity: O(n), where n is the total number of items in the input dictionary.
Auxiliary space: O(m), where m is the maximum depth of the nested dictionaries in the input.

Method 5: Using a Queue and BFS (Breadth-First Search) Approach

• Create an empty queue.
• Enqueue the root node (test_dict) and an empty list to represent the path taken to reach it.
• While the queue is not empty:
  • Dequeue a node and its path.
  • If the node is a dictionary and not empty:
    • For each key-value pair, add the key to the path and enqueue the value and the updated path.
  • If the node is a leaf node and its key is in the key_list, yield the key-value pair.
• Return the result dictionary.

The original dictionary is : {'gfg': {'is': {'best': 3}}, 'for': {'all': 4}, 'Lazyroar': 5}
The extracted values : {'Lazyroar': 5, 'best': 3}

Time complexity: O(N), where N is the total number of elements in the dictionary.
Auxiliary space: O(N), where N is the maximum size of the queue.