Sometimes, while working with Python, we can have a problem in which we need to work with Graph data represented in form of a Dictionary. In this, we may need to check for all the leaf and non-lead nodes. This kind of problem has direct applications in algorithms of Machine Learning. Let’s discuss a way in which this task can be performed.
Input : test_dict = {‘Gfg’: {‘is’: 2, ‘best’: 1}}
Output : {‘leaf’: 2, ‘non-leaf’: 1}Input : test_dict = {‘Gfg’: {‘best’: 2}}
Output : {‘non-leaf’: 1, ‘leaf’: 1}
Method 1: Using recursion + isinstance() + loop
The combination of the above functionalities can be used to solve this problem. In this, we recur for the inner nesting using recursion and check for leaves or non-leaves by value types using isinstance().
Python3
# Python3 code to demonstrate working of # Leaf and Non-Leaf Nodes Dictionary# Using recursion + isinstance() + loopdef hlpr_fnc(dict1, res = {'non-leaf':0, 'leaf':0}): #res['non-leaf'] += 1 nodes = dict1.keys() for node in nodes: subnode = dict1[node] if isinstance(subnode, dict): res['non-leaf'] += 1 hlpr_fnc(subnode, res) else: res['leaf'] += 1 return res# initializing dictionarytest_dict = {'a': {'b': 1, 'c': {'d': {'e': 2, 'f': 1}}, 'g': {'h': {'i': 2, 'j': 1}}}}# printing original dictionaryprint("The original dictionary : " + str(test_dict))# Leaf and Non-Leaf Nodes Dictionary# Using recursion + isinstance() + loopres = hlpr_fnc(test_dict) # printing result print("The leaf and Non-Leaf nodes : " + str(res)) |
Output:
The original dictionary : {'a': {'b': 1, 'c': {'d': {'e': 2, 'f': 1}}, 'g': {'h': {'i': 2, 'j': 1}}}}
The leaf and Non-Leaf nodes : {'non-leaf': 5, 'leaf': 5}
Time Complexity: O(n), where n is the number of nodes in the dictionary.
Auxiliary Space: O(n)
Method 2 : Using stack and loop
- Initialize two variables, non_leaf and leaf, to zero.
- Create an empty list stack and append the input dictionary to it.
- Use a while loop to iterate over the stack until it is empty.
- Within the loop, pop the last dictionary from the stack.
- For each key-value pair in the popped dictionary, increment non_leaf by 1 if the value is a dictionary and append it to the stack. Otherwise, increment leaf by 1.
- Return a dictionary with non-leaf and leaf as keys and their respective counts as values.
Python3
def leaf_and_nonleaf_nodes(dict1): non_leaf = 0 leaf = 0 stack = [dict1] while stack: curr_dict = stack.pop() for val in curr_dict.values(): if isinstance(val, dict): non_leaf += 1 stack.append(val) else: leaf += 1 return {'non-leaf': non_leaf, 'leaf': leaf}# initializing dictionarytest_dict = {'a': {'b': 1, 'c': {'d': {'e': 2, 'f': 1}}, 'g': {'h': {'i': 2, 'j': 1}}}}# printing original dictionaryprint("The original dictionary : " + str(test_dict))# Leaf and Non-Leaf Nodes Dictionary# Using stack and loopres = leaf_and_nonleaf_nodes(test_dict) # printing result print("The leaf and Non-Leaf nodes : " + str(res)) |
The original dictionary : {'a': {'b': 1, 'c': {'d': {'e': 2, 'f': 1}}, 'g': {'h': {'i': 2, 'j': 1}}}}
The leaf and Non-Leaf nodes : {'non-leaf': 5, 'leaf': 5}
Time complexity: O(N), where N is the number of nodes in the input dictionary.
Auxiliary space: O(N), where N is the maximum number of nodes stored in the stack at any given time.
Method 3 :Using a queue:
Algorithm:
- Initialize two variables non_leaf and leaf to 0.
- Create a deque and append the input dictionary to it.
- While the deque is not empty, perform the following steps:
a. Pop the leftmost element from the deque and assign it to the curr_dict variable.
b. For each value in curr_dict, do the following:
i. Check if the value is a dictionary.
ii. If the value is a dictionary, increment the non_leaf variable and append the value to the deque.
iii. If the value is not a dictionary, increment the leaf variable. - Create a dictionary with the non-leaf and leaf variables as values and return it.
Python3
from collections import dequedef leaf_and_nonleaf_nodes_queue(dict1): non_leaf = 0 leaf = 0 queue = deque([dict1]) while queue: curr_dict = queue.popleft() for val in curr_dict.values(): if isinstance(val, dict): non_leaf += 1 queue.append(val) else: leaf += 1 return {'non-leaf': non_leaf, 'leaf': leaf}# initializing dictionarytest_dict = {'a': {'b': 1, 'c': {'d': {'e': 2, 'f': 1}}, 'g': {'h': {'i': 2, 'j': 1}}}}# printing original dictionaryprint("The original dictionary : " + str(test_dict))# Leaf and Non-Leaf Nodes Dictionary# Using queueres = leaf_and_nonleaf_nodes_queue(test_dict)# printing resultprint("The leaf and Non-Leaf nodes : " + str(res))#This code is contributed by Jyothi pinjala |
The original dictionary : {'a': {'b': 1, 'c': {'d': {'e': 2, 'f': 1}}, 'g': {'h': {'i': 2, 'j': 1}}}}
The leaf and Non-Leaf nodes : {'non-leaf': 5, 'leaf': 5}
Time Complexity: O(N), where N is the total number of elements in the input dictionary. This is because each element in the dictionary is visited only once.
Auxiliary Space: O(N), where N is the total number of elements in the input dictionary. This is because the deque used to store the dictionary elements can potentially store all N elements.
