How to create a tree from a large, sorted list of dictionaries?

Question

Python

There is a list like this:

[
    {
        "link": "Computers/",
        "parent": None
    },
    {
        "link": "Computers/Internet/",
        "parent": "Computers/"
    },
    {
        "link": "Computers/Internet/Avatars/",
        "parent": "Computers/Internet/"
    },
...
    {
        "link": "Computers/Internet/Forums/",
        "parent": "Computers/Internet/"
    },
...
]

It needs to be converted to a tree structure like this:

{
        "link": "Computers/",
        "parent": None,
        "children": [
            {
                "link": "Computers/Internet/",
                "parent": "Computers/",
                "children": [
                    {
                        "link": "Computers/Internet/Avatars/",
                        "parent": "Computers/Internet/",
                        "children": [...]
                    },
                    {
                        "link": "Computers/Internet/Forums/",
                        "parent": "Computers/Internet/",
                        "children": [...]
                    }
                ]
            },
        ]
    }

Since the nesting of the original list is large, recursion does not work - it gives: "Maximum recursion depth exceeded". Tried setting the value:

import sys
sys.setrecursionlimit(100000)

Then the interpreter crashes completely with an error.
Please tell me the solution?

Answer 1

I threw it on a piece of paper, I did not check the performance. O(n) complexity, provided the array is sorted.

def transform(data):
    temp = {}

    for raw_item in data:
        item = {
            'link': raw_item['link'],
            'parent': raw_item['parent'],
            'children': [],
        }

        temp[item['link']] = item

        if not item['parent']:
            parent = item
        else:
            temp[item['parent']]['children'].append(item)

    return parent

if __name__ == '__main__':
    res = transform(sorted(data, key=lambda x: x['link']))

Answer 2

Without recursion:
1. First sort by the number of ancestors.
2. Then for each element of the list (for each of its last leaf) look for descendants found, put them inside the ancestor (into the tree) and remove them from the list.
3. Then we check whether there are elements with single ancestors, if there are, then again to point 2.
The complexity here will probably be O (n * n)