Prerequisite: Nested dictionary The task is to find the depth of given dictionary in Python. Let’s discuss all different methods to do this task. Examples:
Input : {1:'a', 2: {3: {4: {}}}}
Output : 4
Input : {'a':1, 'b': {'c':'geek'}}
Output : 3
Approach #1 : Naive Approach A naive approach in order to find the depth of a dictionary is to count the number of opening curly braces. But, one drawback of this approach is that it would only work if the input is correct.
Python3
# Python3 Program to find depth of a dictionarydef dict_depth(dic, level = 1): str_dic = str(dic) counter = 0 for i in str_dic: if i == "{": counter += 1 return(counter) # Driver code dic = {1:'Geek', 2: {3: {4: {}}}}print(dict_depth(dic)) |
4
Time complexity: O(n), where n is the number of key-value pairs in the dictionary.
Auxiliary space: O(n), to store the keys and values in dictionary.
Approach #2: Using recursion In this method we use recursion with max() function which picks the greatest depth for the current dictionary under scrutiny at each level.
Python3
# Python3 Program to find depth of a dictionarydef dict_depth(dic, level = 1): if not isinstance(dic, dict) or not dic: return level return max(dict_depth(dic[key], level + 1) for key in dic)# Driver code dic = {1:'a', 2: {3: {4: {}}}}print(dict_depth(dic)) |
4
Another version of the recursive solution is to use map() function by which the values of the inner dictionary is mapped to the called function.
Python3
# Python3 Program to find depth of a dictionarydef dict_depth(my_dict): if isinstance(my_dict, dict): return 1 + (max(map(dict_depth, my_dict.values())) if my_dict else 0) return 0# Driver code my_dict = {1:'a', 2: {3: {4: {}}}}print(dict_depth(my_dict)) |
4
Approach #3: Iterative Solution In this approach, we save the nested key and its initial depth in a variable, say p_dict. Now, start a loop for p_dict, and keep popping values while digging deeper for nested dictionaries.
Python3
# Python3 Program to find depth of a dictionarydef dict_depth(myDict): Ddepth = 1 obj = [(k, Ddepth + 1) for k in myDict.values() if isinstance(k, dict)] max_depth = 0 while(obj): n, Ddepth = obj.pop() max_depth = max(max_depth, Ddepth) obj = obj + [(k, Ddepth + 1) for k in n.values() if isinstance(k, dict)] return max_depth # Driver code myDict = {1:'a', 2: {3: {4:{}}}}print(dict_depth(myDict)) |
4
Approach #4: Using a stack: You can use a stack to keep track of the current depth and iterate over the dictionary to find the maximum depth.
The dict_depth() function takes in a dictionary as an argument and returns the depth of the dictionary, i.e. the number of nested dictionaries within the original dictionary.
The function starts by initializing a stack with the first key-value pair in the dictionary and a depth of 1. It also initializes a variable max_depth to 1.
Then, the function enters a while loop that iterates over the stack. At each iteration, the function pops the key-value pair from the top of the stack and assigns the values to the variables curr_dict and depth, respectively.
Next, the function iterates over the key-value pairs in curr_dict using a for loop. For each key-value pair, if the value is a dictionary, the function adds the dictionary and the current depth + 1 to the stack. This allows the function to keep track of the depth as it iterates over the nested dictionaries.
Finally, the function updates the maximum depth using the max() function and returns it at the end of the function.
Python3
def dict_depth(dic): # Initialize a stack with the first key-value pair in the dictionary stack = [(dic, 1)] # Initialize the maximum depth max_depth = 1 # Iterate over the stack while stack: # Pop the key-value pair from the top of the stack curr_dict, depth = stack.pop() # If the value is a dictionary, add its key-value pairs to the stack for key, value in curr_dict.items(): if isinstance(value, dict): stack.append((value, depth + 1)) # Update the maximum depth max_depth = max(max_depth, depth) # Return the maximum depth return max_depthdic = {1:'a', 2: {3: {4: {}}}}print(dict_depth(dic))#This code is contributed by Edula Vinay Kumar Reddy |
4
Time complexity: O(n)
Auxiliary Space: O(n)
Approach#6: using queue
This approach involves using a queue to perform a breadth-first search (BFS) on the dictionary. We start by adding the dictionary to the queue along with a depth of 1. Then we pop the first element from the queue, and for each key in the element, we add the corresponding value to the queue along with the depth of the parent element plus 1. We repeat this process until the queue is empty, and the maximum depth found so far is the depth of the dictionary.
Algorithm
- Initialize depth to 0 and create an empty queue
- Add the input dictionary and a depth of 1 to the queue
- While the queue is not empty:
- Pop the first element from the queue
- For each key in the element, add the corresponding value to the queue along with the depth of the parent element plus 1
- Update depth if the new depth is greater than the current depth
- Return depth.
Python3
from collections import dequedef find_depth(d): if not isinstance(d, dict): return 0 depth = 0 q = deque([(d, 1)]) while q: node, node_depth = q.popleft() depth = max(depth, node_depth) for key in node: if isinstance(node[key], dict): q.append((node[key], node_depth + 1)) return depthd = {1:'a', 2: {3: {4: {}}}}print(find_depth(d)) |
4
Time Complexity: O(n), where n is the number of nodes in the dictionary.
Space Complexity: O(w), where w is the maximum width of the dictionary. In the worst case, the entire dictionary will be added to the queue, which can lead to a space complexity of O(n).
