test work

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 dip_search(root: dict, key: str):
    if key in root.keys():
        return root[key]
    else:
        for child in root.keys():
            result = dip_search(root[child], key)
            if result != None:
                return result


def to_tree(source):
    node = {}
    for root, path in source:
        if root == None:
            node[path] = {}
        else:
            result = dip_search(node, root)
            if result != None:
                result[path] = {}
    return node

assert to_tree(source) == expected