gistfile1.txt

m collections import defaultdict

up = {}

for r in messages:
    if 'parent' in r.keys():
        up[r['id']] = r['parent']
    else:
        up[r['id']] = None

ancestors = set()
for k, v in up.items():
    if not v:
        ancestors.add(k)
    elif v not in up.keys():
        ancestors.add(v)

print(ancestors)

def find_ancestor(ancestors, id):
    parent = ancestors.get(id, id)
    if parent and parent != id:
        return find_ancestor(ancestors, parent)
    else:
        return id

threads = defaultdict(list)

for message in messages:
    id = message['id']
    ancestor = find_ancestor(up, id)
    if ancestor != id:
        threads[ancestor].append(id)

print(threads)