Build a tree given only a list of parent-child relationships in Python

Question

I have a list of parent-child relationship as the following example: (node0 -> node1 means that node0 is the parent of node1)

node0 -> node1
node1 -> node2
node1 -> node3
node0 -> node4

What I want to construct is a dictionary that captures the tree relationships; where each parent node maps to a dictionary containing its children, and if a node is a leaf node, it will just maps to an empty list. Meaning out of this list I'd get:

{node0:{node1:{node2:[], node3:[]}, node4:[]}}

What's the best way for me to approach this?

Answer 1

You can do this by registering all nodes in one flat dictionary, and reuse those values also for nesting.

However, there should be no lists involved. All values associated with keys will be dictionaries.

To determine what is the root, find out which node is never used as a child.

edges = [
    ("node0", "node1"),
    ("node1", "node2"),
    ("node1", "node3"),
    ("node0", "node4")
]

nodes = {}
root = next(iter(set(start for start, _ in edges) - set(end for _, end in edges)))
for start, end in edges:
    nodes.setdefault(start, {})[end] = nodes.setdefault(end, {}) 

tree = { root: nodes[root] }
print(tree)