Convert dict pairs to dict tree

dict_pairs_to_tree.py

source = [
    (None, 'a'),
    (None, 'b'),
    (None, 'c'),
    ('a', 'a1'),
    ('a', 'a2'),
    ('a2', 'a21'),
    ('a2', 'a22'),
    ('b', 'b1'),
    ('b1', 'b11'),
    ('b11', 'b111'),
    ('b', 'b2'),
    ('c', 'c1'),
]

expected = {
    'a': {'a1': {}, 'a2': {'a21': {}, 'a22': {}}},
    'b': {'b1': {'b11': {'b111': {}}}, 'b2': {}},
    'c': {'c1': {}},
}


def to_tree(_input):

    output = {}

    for i, kv in enumerate(_input):
        if kv[0] is None:
            output[kv[1]] = {}
        else:
            def iterdict(d):
                for k, v in d.items():
                    if k == kv[0]:
                        d[k][kv[1]] = {}
                        return True
                    elif isinstance(v, dict):
                        ret = iterdict(v)
                        if ret is True:
                            return True

            iterdict(output)

    return output


assert to_tree(source) == expected