Build a tree from a list

Question

I need to build a dict in form of a tree from a list. The first keys are the last elements of the list.

current = [['A1'], ['B1', 'A1'], ['B2', 'A1'], ['C1', 'B2', 'A1'], ['D2', 'C1', 'B2', 'A1'], ['D1', 'C1', 'B2', 'A1'], ['A2']]

expected = {
  'A1': {
    'B1': None,
    'B2': {
      'C1': {
        'D1': None,
        'D2': None
      },
    },
  },
  'A2': None
}

I have tried something with default dict, but no success in make it recursively, and i don't know if it's the correct way.

result = defaultdict(list)
for e in current:
    result[e[-1]].append(e)

I have tried some solutions with defaultdict, but no success. I have no idea how to convert this list to that dict — Gabriel Weich, Feb 11 '19 at 13:29
There is no question. Having no idea is not a question. NB: the question should be specific. There are lots of resources and tutorials, so surely you can make a start. Tell us where you bump into an issue. — trincot, Feb 11 '19 at 13:33
Why the expected is wrong? The question is how to transform one input in specific form in one output. Why is it not minimal , complete and verifiable? — Gabriel Weich, Feb 11 '19 at 13:39
How can we know whether what you tell us is "expected" is wrong? A task ("transforming") is not a question. — trincot, Feb 11 '19 at 13:41
Expected is the result that I want from that input, someone said that maybe it was wrong, I don't know why. — Gabriel Weich, Feb 11 '19 at 13:44
Maybe the correct word is convert. How to convert that list into that dict? — Gabriel Weich, Feb 11 '19 at 13:46
@GabrielNoth StackOverflow is not intended to be a code writing sevice. We are happy to help, but please show some effort from your part (which include reading about the subject and trying a few things yoursefl). — Ralf, Feb 11 '19 at 13:47
"Someone said that maybe it was wrong, I don't know why": this really needs more explanation? If you don't know what is expected, then how should we know? — trincot, Feb 11 '19 at 13:49
Sorry if I was not clear with the question, but Lordfirespeed understood this. — Gabriel Weich, Feb 11 '19 at 13:57

score 2 · Accepted Answer · answered Feb 11 '19 at 13:51

2

This doesn't have the None which you wanted, instead providing empty dict objects. However, it does form the expected tree from the list provided:

current = [['A1'], ['B1', 'A1'], ['B2', 'A1'], ['C1', 'B2', 'A1'], ['D2', 'C1', 'B2', 'A1'], ['D1', 'C1', 'B2', 'A1'], ['A2']]
tree = {}

for item in current:
    currentdict = tree
    for key in item[::-1]:
        if key not in currentdict.keys():
            currentdict[key] = {}
        currentdict = currentdict[key]

expected = {
  'A1': {
    'B1': {},
    'B2': {
      'C1': {
        'D1': {},
        'D2': {}
      },
    },
  },
  'A2': {}
}

print(tree == expected)  # True

answered Feb 11 '19 at 13:51

Lordfirespeed

164
6

".keys()" is not necessary in "if key not in currentdict.keys():", correct? – Gabriel Weich Feb 11 '19 at 14:50
@GabrielNoth No, it's not necessary, as _key in dict_ will read the dict as a list of keys - however it is more concise. – Lordfirespeed Feb 11 '19 at 14:59
@Lordfirespeed it's *less* concise, it's literally more characters – jonrsharpe Feb 11 '19 at 15:31
@jonrsharpe fair point. I'll often take comprehensive and legible over concise code though. – Lordfirespeed Feb 11 '19 at 17:21

score -1 · Answer 2 · answered Feb 11 '19 at 13:51

Here is one way to do it.

First we will borrow methods from --> here

import pprint
from operator import getitem
from functools import reduce

def getdict(dict_, mappings):
    return reduce(getitem, mappings, dict_)

def setdict(dict_, mappings):
    getdict(dict_, mappings[:-1])[mappings[-1]] = dict()

d = dict()

for cur in current:
    c = cur[::-1]
    setdict(d, c)

pprint.pprint(d)

{'A1': {'B1': {}, 'B2': {'C1': {'D1': {}, 'D2': {}}}}, 'A2': {}}

Build a tree from a list

2 Answers2