Given a list of lists, write a Python program to convert the given list of lists into a tree-like dictionary.
Examples:
Input : [[1], [2, 1], [3, 1], [4, 2, 1], [5, 2, 1], [6, 3, 1], [7, 3, 1]]
Output : {1: {2: {4: {}, 5: {}}, 3: {6: {}, 7: {}}}}
Input : [['A'], ['B', 'A'], ['C', 'A'], ['D', 'C', 'A']]
Output : {'A': {'C': {'D': {}}, 'B': {}}}
Method #1 : Naive Method This is a Naive approach in which we use two for loops to traverse the list of lists. We initialize the empty dictionary ‘tree’ to currTree and each time we check if the key (list of list’s item) is included in the currTree or not. If not, include it in the currTree, otherwise do nothing. Finally, assign the currTree[key] to currTree.
Python3
# Python3 program to Convert a list# of lists into Dictionary (Tree form)def formTree(list): tree = {} for item in list: currTree = tree for key in item[::-1]: if key not in currTree: currTree[key] = {} currTree = currTree[key] return tree# Driver Codelst = [['A'], ['B', 'A'], ['C', 'A'], ['D', 'C', 'A']]print(formTree(lst)) |
{'A': {'B': {}, 'C': {'D': {}}}}
Time complexity: O(n*m), where n is the number of lists in the input list and m is the maximum length of a list in the input list.
Auxiliary space: O(k), where k is the number of unique keys in the input list.
Method #2 : Using reduce() The reduce() function is used to apply a particular function passed in its argument to all of the list elements mentioned in the sequence passed along. We will use reduce() to traverse the dictionary and reuse getTree() to find the location to store the value for setTree(). All but the last element in mapList is needed to find the ‘parent’ dictionary to add the value to, then use the last element to set the value to the right key.
Python3
# Python3 program to Convert a list# of lists into Dictionary (Tree form)from functools import reducefrom operator import getitemdef getTree(tree, mappings): return reduce(getitem, mappings, tree) def setTree(tree, mappings): getTree(tree, mappings[:-1])[mappings[-1]] = dict()# Driver Codelst = [['A'], ['B', 'A'], ['C', 'A'], ['D', 'C', 'A']]tree ={}for item in lst: setTree(tree, item[::-1])print(tree) |
{'A': {'B': {}, 'C': {'D': {}}}}
Time Complexity: O(n*m) where n is the length of the input list and m is the maximum length of a sublist.
Auxiliary Space: O(k) where k is the number of nodes in the resulting tree.
Method 3: Using the reduce() function
step-by-step approach
- Initialize an empty dictionary tree.
- Iterate over each path in the input list lst.
- Initialize a variable current to be the tree dictionary.
- Iterate over each node in the current path.
- Check if the current node is already a key in the current dictionary.
- If the current node is not a key in the current dictionary, add it as a key with an empty dictionary as its value.
- Update the current variable to be the dictionary corresponding to the current node.
- Once all the nodes in the current path have been added to the dictionary tree, move on to the next path in the input list.
- Once all the paths in the input list have been processed, return the tree dictionary.
- The resulting dictionary tree will have a nested structure corresponding to the input list. Each sub-list in the input list corresponds to a path in the dictionary, with each element in the sub-list corresponding to a nested dictionary.
Python3
def create_tree(lst): tree = {} for path in lst: current = tree for node in path: if node not in current: current[node] = {} current = current[node] return treelst = [['A'], ['B', 'A'], ['C', 'A'], ['D', 'C', 'A']]tree = create_tree(lst)print(tree) |
{'A': {}, 'B': {'A': {}}, 'C': {'A': {}}, 'D': {'C': {'A': {}}}}
In terms of time and space complexity, this approach has a time complexity of O(nm), where n is the length of the input list and m is the maximum length of any path in the list. The space complexity is also O(nm), since we need to store a dictionary for each node in the tree. However, in practice,
the auxiliary space is likely to be much lower, since many of the paths in the input list are likely to share common prefixes, and thus share dictionaries in the resulting tree.
