Python – Test for empty Nested Records

Sometimes, while working with Python dictionaries, we can have a problem in which we need to test if a particular dictionary has nested records, and all of them is empty, i.e with no key or no value in case of list. This kind of problem is quite common in data domains such as Data Science. Let’s discuss certain way in which this task can be performed.

Input : test_dict = {‘Gfg’: [], ‘neveropen’: {}} 
Output : True 

Input : test_dict = {‘Gfg’: 4} 
Output : False

Method #1 : Using recursion + all() + isinstance() The combination of above functionalities can be used to solve this problem. In this, we check for all nesting using all(), recursion and isinstance() is used to test for dictionary or list. 

The time complexity of this approach is O(n), where n is the total number of elements in the input dictionary. 

The auxiliary space complexity of this approach is also O(n), as the function call stack grows as the recursion depth increases. 

Method #2: Using recursion + a flag variable

Instead of using the built-in functions all() or any(), we can use a flag variable to keep track of whether any non-empty nested record has been found in the dictionary. If the flag variable remains False after checking all the nested records, it means the dictionary is empty.

The original dictionary : {'Gfg': [], 'is': {'best': [], 'for': {}}, 'neveropen': {}}
Is dictionary without data ? : True

Time complexity: O(N), where N is the number of elements in the nested dictionary..
Auxiliary space: O(N), as the function calls itself recursively for each non-empty nested record in the dictionary. 

Method #3: Using iteration with stack

Step 1: Define the function is_dict_empty that takes a dictionary as input and returns True if the dictionary is empty or contains only empty nested records, False otherwise.

Step 2: Initialize a stack with the values of the input dictionary.

Step 3: While the stack is not empty, pop a value from the stack.

Step 4: Check if the popped value is a dictionary.

Step 5: If the popped value is a dictionary and it’s not empty, extend the stack with its values.

Step 6: Check if the popped value is a list.

Step 7: If the popped value is a list and it’s not empty, extend the stack with its values.

Step 8: Check if the popped value is not empty.

Step 9: If the popped value is not empty, return False.

Step 10: If the loop completes, return True.

Step 11: Call the is_dict_empty function with the initialized dictionary as input.

Step 12: Print the result.

The original dictionary: {'Gfg': [], 'is': {'best': [], 'for': {}}, 'neveropen': {}}
Is the dictionary without data? True

The time complexity of this approach is O(n), where n is the number of items in the dictionary. The auxiliary space is O(d), where d is the maximum depth of the nested records.

Method 4: Using a depth-first search algorithm. 

The idea is to traverse the dictionary recursively and keep track of the depth of each key-value pair. If a key-value pair is found at a greater depth than any previous pair, update the maximum depth. At the end, if the maximum depth is 1, then the dictionary is empty.

Step-by-step approach:

• Define a recursive function dfs() that takes a dictionary, a depth variable depth, and max_depth as arguments.
• In dfs(), if the current depth is greater than max_depth, update max_depth.
  • If the dictionary is empty, return True.
  • For each key-value pair in the dictionary, call dfs() with the value as the dictionary and depth+1 as the new depth.
    • If any call to dfs() returns False, return False.
• After the loop, return True if max_depth is 1, else return False.
• In is_dict_empty(), call dfs() with the input dictionary and return the result.

Below is the implementation of the above approach:

Is dictionary without data ? : True

Time Complexity: O(N), where N is the number of key-value pairs in the dictionary. 
Auxiliary Space: O(H), where H is the maximum depth of the dictionary.