Python | Build tree from list [(parent, child),]

scratch.py

def to_tree(source):
    parents = sorted([pair[1] for pair in source if pair[0] is None])
    mod_source = sorted([pair for pair in source if pair[0] is not None])

    def compile_branch(parent):
        batch = []

        for pair in mod_source:
            _parent, _child = pair

            if _parent == parent:
                batch.append(pair)

        if len(batch) > 1:
            sibling = dict()
            sibling[parent] = {}

            for pair in batch:
                _parent, _child = pair
                sibling[parent].update(compile_branch(_child))
            return sibling

        if len(batch) == 1:
            _parent, _child = batch[0]
            return {_parent: compile_branch(_child)}

        return {parent: {}}

    tree = {}

    for parent in parents:
        tree[parent] = compile_branch(parent)[parent]

    return tree


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'),
]

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

assert to_tree(source) == excepted, "Wrong !!!"
print('Excellency !!!')