Python | Convert list of lists to tree dictation



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 a list of lists. We are initializing an empty dictionary & # 39; tree & # 39; for currTree and each time we check if the key (list of list items) is included in currTree or not. If not, include it in currTree , otherwise do nothing. Finally, assign currTree [key] to currTree .

# Python3 list conversion program
# of lists to 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 code

lst = [[[ `A` ], [ `B` , ` A ` ], [ ` C` , `A` ], [ ` D` , `C` , ` A` ]]

print (formTree (lst))

Exit:

 {`A`: { `B`: {},` C`: {`D`: {}}}} 

Method # 2: Using reduce ()
The reduce () function is used to apply a specific function passed in its argument, to all the elements of the list mentioned in the passed sequence. We will use getTree () reduce () to traverse the dictionary and reuse getTree () to find a place to store the value for setTree () . Everything but the last element in the mapList is needed to find the "parent" dictionary to add the value, and then use the last element to set the value for the right key.

# Python3 list conversion program
# lists to dictionary (tree form)

 

from functools import reduce

from operator import getitem

 

def getTree (tree, mappings):

  return reduce (getitem, mappings, tree)

 

def setTree (tree, mappings):

getTree (tree, mappings [: - 1 ]) [mappings [ - 1 ]] = dict ()

 
Driver code

lst = [[ `A` ], [ ` B` , `A` ], [ `C` , ` A` ], [ `D` , `C` , ` A` ]]

tree = {}

for item in lst:

setTree (tree, item [:: - 1 ])

 

print (tree)

Exit:

 {`A`: {` B` : {}, `C`: {` D`: {}}}}