How to flatten a nested dictionary without recursion?

Question

I came across this function that can flatten a dictionary:

def flatten(dictionnary, container=None):
    if container is None:
        container = []
    for k, v in dictionnary.items():
        container.append(k)
        if v:
            flatten(v, container)
    return container

to test it I created a dictionnay that is nested n times like so:

nesteddict = {}
for i in range(n, 0, -1):
    emptydict = {}
    emptydict[i] = nesteddict
    nesteddict = emptydict

the function works while n is less than 999, otherwise it hit recursion limit:

RecursionError: maximum recursion depth exceeded while calling a Python object

so after a little bit of searching it seems that any recursive function can rewritten to iteration but I cant see how it could be done for the function I have to produce the same results.

Another weird problem I came across while playing with this is if I try the code below for n >= 998:

nesteddict = {}
for i in range(n, 0, -1):
    emptydict = {}
    emptydict[i] = nesteddict
    nesteddict = emptydict
print(nesteddict)

I get recursion error:

RecursionError: maximum recursion depth exceeded while getting the repr of an object

which is weird since I dont see any recursion here.

Answer 1

Logically, nested dictionaries (and lists) is a kind of recursion, so if you want to avoid logical recursion, that's impossible.

But, since recursion is just recursion, you can keep a stack of your own and simulate that in a loop:

def flatten(dct, c=None):
    if c is None:
        c = []
    stack = [dct]
    while stack:  # non-empty
        d = stack.pop()
        for k, v in d.items():
            c.append(k)
            if v:
                stack.append(v)
    return c

This function well emulates the behavior of function recursion, with a custom stack.

There's one potential downside: Theoretically, a dictionary like

{1: None, 2: {3: None, 4: None}, 5: None}

should be flattened as [1, 2, 3, 4, 5], while this method would give [1, 2, 5, 3, 4]. This is much like a DFS search vs a BFS search on a graph.

But, since dictionary is unordered, this shouldn't be a big matter (unless you're using collections.OrderedDict), and that's why I say this is a potential downside.

Answer 2

Instead of saving the dict in the stack, you should save the item's iterator in stack.

This way, you can resume the iterator on command.

Also because you're pausing and resuming the execution of iterators in order, the result will always be according to the order of the dict.

By the way, @iBug, dicts are ordered as per Python's specification from 3.7

def flatten(dictionary, container=None):
    if container is None:
        container = []
    iterators = []
    iterator = iter(dictionary.items())
    while True:
        for k, v in iterator:
            container.append(k)
            if v:
                # Save the current iterator for later
                iterators.append(iterator)
                # Run on the new dict
                iterator = iter(v.items())
                break

        # Current iterator is done, fetch the next one
        else:
            try:
                iterator = iterators.pop()
            except IndexError:
                return container

print(flatten({1: None, 2: {3: None, 4: None}, 5: None}))
[1, 2, 3, 4, 5]

Answer 3

Flattening can be interpreted variously; if you want to flatten a dictionary into a dictionary with dot separated keys, this approach may work:

def flatten(it=None, sep="."):

    ot = {}

    if isinstance(it, dict):
        stack = list(it.items())[::-1]
    elif isinstance(it, list):
        stack = list(enumerate(it))[::-1]

    while stack:

        head = stack.pop()

        if isinstance(head[1], dict):
            stack = stack + [(f'{head[0]}{sep}{item[0]}', item[1]) for item in head[1].items()][::-1]
        elif isinstance(head[1], list):
            stack = stack + [(f'{head[0]}{sep}{item[0]}', item[1]) for item in enumerate(head[1])][::-1]
        else:
            ot[head[0]] = head[1]

    return ot

Given the input: {'b': 2, 'a': 1, 'c': {'a': 1, 'b': [1, 2, 3]}, 'd': [1, 2, {'b': 1, 'a': 2}]}

The output is:

{'b': 2,
 'a': 1,
 'c.a': 1,
 'c.b.0': 1,
 'c.b.1': 2,
 'c.b.2': 3,
 'd.0': 1,
 'd.1': 2,
 'd.2.b': 1,
 'd.2.a': 2}

Answer 4

You can use pandas.json_normalize document here: https://pandas.pydata.org/docs/reference/api/pandas.json_normalize.html

Answer 5

If you want to do it without recursion, it is impossible.

So Here the solution for the RecursionError.

Based on the doc of python. You could use sys.getrecursionlimit() to see the limit of recursion. You could also use sys.setrecursionlimit() to make the limit upper.