Create a tree from a given dictionary

Question

I have a python dictionary and I would like to create a tree from it. The dictionary is something like this:

dict_={"2":{'parent': "1"},"1":{'parent': None},"3":{'parent': "2"}}

in this case, the root is "1"

I tried to use treelib library but the problem when I iterate on the dictionary and create a node, its parent isn't created yet. For example, if I want to create a node for "2", its parent("1") isn't created yet, so can not do it. Any idea?

Answer 1

You could do the following, using treelib:

from treelib import Node, Tree

dict_ = {"2": {'parent': "1"}, "1": {'parent': None}, "3": {'parent': "2"}}

added = set()
tree = Tree()
while dict_:

    for key, value in dict_.items():
        if value['parent'] in added:
            tree.create_node(key, key, parent=value['parent'])
            added.add(key)
            dict_.pop(key)
            break
        elif value['parent'] is None:
            tree.create_node(key, key)
            added.add(key)
            dict_.pop(key)
            break

tree.show()

Output

1
└── 2
    └── 3

The idea is to add a node only if the parent is present in the tree or the parent is None. When the parent is None add it as root.

Answer 2

You can do the following. First, transform the data structure to a parent-children mapping:

from collections import defaultdict

d = defaultdict(list)  # parent: List[children]
for k, v in dict_.items():
    d[v['parent']].append(k)

Then, starting with the root

root = d[None][0]

tree = Tree()
tree.create_node(root, root)

Create the tree from the top:

agenda, seen = [root], set([root])
while agenda:
    nxt = agenda.pop()
    for child in d[nxt]:
        tree.create_node(child, child, parent=nxt)
        if child not in seen:
            agenda.append(child)
            seen.add(child)