construct_trees.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
This code resolves the problem described in
http://xahlee.info/perl-python/python_construct_tree_from_edge.html

"""

import collections
import json


def construct_trees(edges):
    """Given a list of edges [child, parent], return trees. """
    trees = collections.defaultdict(dict)

    for child, parent in edges:
        trees[parent][child] = trees[child]

    # Find roots
    children, parents = zip(*edges)
    roots = set(parents).difference(children)

    return {root: trees[root] for root in roots}


if __name__ == '__main__':
    edges = [[0, 2], [3, 0], [1, 4], [2, 4], [5, 6], [6, 7], [8, 6]]
    print(json.dumps(construct_trees(edges), indent=2))

I don't understand how this works.
trees[parent][child] = trees[child]
should only work if the nodes are given in the correct order. However it works out of order. How is this possible?

I don't understand how this works.
trees[parent][child] = trees[child]
should only work if the nodes are given in the correct order. However it works out of order. How is this possible?

because the variable "trees "is a default dict , which will automatically construct an object(a empty dict in this case) when key does not exist, so when you access trees[parent], a new dict indicating that parent node will be built if it is not exist at the moment.