CODEWITHSUNDEEP
pythonpython-3.x
Petr Sklyarov
Petr Sklyarov

Reputation: 93

Build a dictionary in the form of a multi-level tree

I get from the database objects that are directory entries from the database which are sorted in a tree:

db_tree = [
{"id":2, "parent_id":1, "level":1,  "name":"parent 1"},
{"id":5, "parent_id":2, "level":2,  "name":"child 1 - 1"},
{"id":6, "parent_id":2, "level":2,  "name":"child 1 - 2"},
{"id":9, "parent_id":2, "level":2,  "name":"child 1- 3"},
{"id":7, "parent_id":5, "level":3,  "name":"child 1 - 1 - 1"},
{"id":11, "parent_id":6, "level":3, "name":"children 2- 1"},
{"id":10, "parent_id":7, "level":4, "name":"child 4 levl parent 1"},
{"id":3, "parent_id":1, "level":1,  "name":"parent 2"},
{"id":13, "parent_id":3, "level":2, "name":"parent 2- 1 - chil"},
{"id":4, "parent_id":1, "level":1,  "name":"parent 3"},
{"id":8, "parent_id":1, "level":1,  "name":"parent 4"}
]

The list is already sorted as a tree, i.e. there is a parent section (level 1), then, if there are children, then the next section of the 1st level. I need to bring this data to this kind of dictionary:

tree = {}
tree['parent 1'] = {}
tree['parent 1']['child 1 - 1'] = {}
tree['parent 1']['child 1 - 1']['child 1 - 1 - 1'] = {}
tree['parent 1']['child 1 - 1']['child 1 - 1 - 1']['child 4 levl parent 1'] = {}
tree['parent 1']['child 1 - 2'] = {}
tree['parent 1']['child 1 - 2']['children 2- 1'] = {}
tree['parent 1']['child 1- 3'] = {}
tree['parent 1']['child1']['child3'] = {} 

tree['parent 2'] = {}
tree['parent 2']['parent 2- 1 - chil'] = {}

tree['parent 3'] = {}
tree['parent 4'] = {}

If anyone came across or did this, please tell me

Upvotes: 1

Views: 573

Answers (3)

mathfux
mathfux

Reputation: 5939

For better code redability and visualisation you can use advantages of networkx:

import networkx as nx
import pprint
G = nx.DiGraph()
for n in db_tree:
    G.add_node(n["name"]) #adds node
    children = [x for x in db_tree if x["id"] == n["parent_id"]]
    if children:
        G.add_edge(n["name"], children[0]["name"]) #add directed edge if it has
nx.draw(G, with_labels=True)

Unfortunately, it has no simple method for converting graph into data structure that is nested dictionary.

Output:

enter image description here

Upvotes: 2

Dylon
Dylon

Reputation: 1750

I would build the tree recursively:

from pprint import pprint


def process_row(row, index, tree):
    if row is None:
        return tree
    parent = index.get(row["parent_id"], None)
    subtree = process_row(parent, index, tree)
    if row["name"] not in subtree:
        subtree[row["name"]] = {}
    return subtree[row["name"]]


def build_tree(db_tree):
    tree = {}
    index = {row["id"]: row for row in db_tree}
    for row in db_tree:
        process_row(row, index, tree)
    return tree


db_tree = [
    {"id": 2, "parent_id": 1, "level": 1,  "name": "parent 1"},
    {"id": 5, "parent_id": 2, "level": 2,  "name": "child 1 - 1"},
    {"id": 6, "parent_id": 2, "level": 2,  "name": "child 1 - 2"},
    {"id": 9, "parent_id": 2, "level": 2,  "name": "child 1- 3"},
    {"id": 7, "parent_id": 5, "level": 3,  "name": "child 1 - 1 - 1"},
    {"id": 11, "parent_id": 6, "level": 3, "name": "children 2- 1"},
    {"id": 10, "parent_id": 7, "level": 4, "name": "child 4 levl parent 1"},
    {"id": 3, "parent_id": 1, "level": 1,  "name": "parent 2"},
    {"id": 13, "parent_id": 3, "level": 2, "name": "parent 2- 1 - chil"},
    {"id": 4, "parent_id": 1, "level": 1,  "name": "parent 3"},
    {"id": 8, "parent_id": 1, "level": 1,  "name": "parent 4"},
]

tree = build_tree(db_tree)
pprint(tree)

Output:

{'parent 1': {'child 1 - 1': {'child 1 - 1 - 1': {'child 4 levl parent 1': {}}},
              'child 1 - 2': {'children 2- 1': {}},
              'child 1- 3': {}},
 'parent 2': {'parent 2- 1 - chil': {}},
 'parent 3': {},
 'parent 4': {}}

Upvotes: 1

Tadhg McDonald-Jensen
Tadhg McDonald-Jensen

Reputation: 21453

you can keep track of a mapping of ID to where it is in the tree and another for the actual tree. 

db_tree = [
{"id":2, "parent_id":1, "level":1,  "name":"parent 1"},
{"id":5, "parent_id":2, "level":2,  "name":"child 1 - 1"},
{"id":6, "parent_id":2, "level":2,  "name":"child 1 - 2"},
{"id":9, "parent_id":2, "level":2,  "name":"child 1- 3"},
{"id":7, "parent_id":5, "level":3,  "name":"child 1 - 1 - 1"},
{"id":11, "parent_id":6, "level":3, "name":"children 2- 1"},
{"id":10, "parent_id":7, "level":4, "name":"child 4 levl parent 1"},
{"id":3, "parent_id":1, "level":1,  "name":"parent 2"},
{"id":13, "parent_id":3, "level":2, "name":"parent 2- 1 - chil"},
{"id":4, "parent_id":1, "level":1,  "name":"parent 3"},
{"id":8, "parent_id":1, "level":1,  "name":"parent 4"}
]

tree = {}
id_to_children = {1: tree}


for entry in db_tree:
    id = entry["id"]
    name = entry["name"]
    parent_id = entry["parent_id"]
    # assume all elements are new, could check if it already exists
    my_children = {}
    id_to_children[id] = my_children
    #this is where we should be added in the tree.
    parent_children = id_to_children[parent_id]
    # add our node as a new child of our parent.
    parent_children[name] = my_children


import pprint

pprint.pprint(tree)

Upvotes: 1

Related Questions