CODEWITHSUNDEEP
pythonpython-3.xdictionarytree
Mon L
Mon L

Reputation: 45

Print a tree from a given dictionary

I have a python dictionary and I would like to create a tree from it. I`m using the treelib library to print it. The dictionary looks something like this:

my_dict = {'S': {1: 'AbB', 2: 'bbS'}, 'AbB': {1: 'bAbbB', 2: 'abB'}, 'bAbbB': {}, 'abB': {1: 'abAaA', 2: 'abbBB', 3: 'abb'}, 'abAaA': {}, 'abbBB': {}, 'abb': {}, 'bbS': {}}

My first key is always the root and the values of the key are its children. For the keys that have empty values, it means they don't have a subtree.

I tried doing it in a recursive way and this but get all kind of errors, I think im approaching the problem in the wrong way:

added = set()
tree = Tree()
while dict_:
    i = 1
    for key, value in dict_.items():
        if key in added:
            tree.create_node(value[i], value[i], parent=key)
            added.add(key)
            dict_.pop(key)
            i += 1
            break
        elif key not in added:
            tree.create_node(key, key)
            added.add(key)
            dict_.pop(key)
            break
tree.show()

My derised output would be something like this

S
├── AbB
│   ├── abB
│   │   ├── abAaA
│   │   ├── abb
│   │   └── abbBB
│   └── bAbbB
└── bbS

Any help or ideas on how to do this? I've read many posts and tried many different methods and didn't make it work.

Upvotes: 0

Views: 2446

Answers (1)

Grismar
Grismar

Reputation: 31319

There are two problems inherent to your data structure:

  • What if two children have the same label? I.e. what if the root has children 'A' and 'B', but both 'A' and 'B' have a child called 'a'? We can only assume that never happens, but in realistic trees (for instance a file system) it's common (i.e. two folders can both have sub-folders with the same name, but different contents)

  • What if a loop is introduced, like {'S': {'a'}, 'a': {'b'}, 'b': {'a'}}

I'm going to assume your tree has neither loops nor duplicates, but that's quite an assumption.

Since your data structure has no way of telling on what level its values are, the best way to go about this would be: whenever you add a node, first check if it has children and add them, before moving on to the siblings:

from treelib import Node, Tree

my_dict = {'S': {1: 'AbB', 2: 'bbS'}, 'AbB': {1: 'bAbbB', 2: 'abB'}, 'bAbbB': {}, 'abB': {1: 'abAaA', 2: 'abbBB', 3: 'abb'}, 'abAaA': {}, 'abbBB': {}, 'abb': {}, 'bbS': {}}


def add_children(data, tree, node):
    if node in data:
        for key in range(1, len(data[node])+1):
            tree.create_node(data[node][key], data[node][key], parent=node)
            add_children(data, tree, data[node][key])


def main():
    tree = Tree()
    root = 'S'
    tree.create_node(root, root)
    add_children(my_dict, tree, root)
    tree.show()


if __name__ == '__main__':
    main()

This is an example where a recursive solution is elegant and simple, but keep in mind that recursion comes at a price. It's not always the best performing and there will be a limit to how deep it can go. You'll have to decide based on the actual data if recursion is the best solution or whether you can rewrite to an iterative solution.

Upvotes: 2

Related Questions