How to completely traverse a complex dictionary of unknown depth?

Question

Importing from JSON can get very complex and nested structures. For example:

{u'body': [{u'declarations': [{u'id': {u'name': u'i',
                                       u'type': u'Identifier'},
                               u'init': {u'type': u'Literal', u'value': 2},
                               u'type': u'VariableDeclarator'}],
            u'kind': u'var',
            u'type': u'VariableDeclaration'},
           {u'declarations': [{u'id': {u'name': u'j',
                                       u'type': u'Identifier'},
                               u'init': {u'type': u'Literal', u'value': 4},
                               u'type': u'VariableDeclarator'}],
            u'kind': u'var',
            u'type': u'VariableDeclaration'},
           {u'declarations': [{u'id': {u'name': u'answer',
                                       u'type': u'Identifier'},
                               u'init': {u'left': {u'name': u'i',
                                                   u'type': u'Identifier'},
                                         u'operator': u'*',
                                         u'right': {u'name': u'j',
                                                    u'type': u'Identifier'},
                                         u'type': u'BinaryExpression'},
                               u'type': u'VariableDeclarator'}],
            u'kind': u'var',
            u'type': u'VariableDeclaration'}],
 u'type': u'Program'}

What is the recommended way to walk complex structures like the above?

Apart of a few list there are mostly dictionaries, the structure can become even more imbricated so I need a general solution.

score 71 · Accepted Answer · edited Jul 18 '22 at 12:44

You can use a recursive generator for converting your dictionary to flat lists.

def dict_generator(indict, pre=None):
    pre = pre[:] if pre else []
    if isinstance(indict, dict):
        for key, value in indict.items():
            if isinstance(value, dict):
                for d in dict_generator(value, pre + [key]):
                    yield d
            elif isinstance(value, list) or isinstance(value, tuple):
                for v in value:
                    for d in dict_generator(v, pre + [key]):
                        yield d
            else:
                yield pre + [key, value]
    else:
        yield pre + [indict]

It returns

[u'body', u'kind', u'var']
[u'init', u'declarations', u'body', u'type', u'Literal']
[u'init', u'declarations', u'body', u'value', 2]
[u'declarations', u'body', u'type', u'VariableDeclarator']
[u'id', u'declarations', u'body', u'type', u'Identifier']
[u'id', u'declarations', u'body', u'name', u'i']
[u'body', u'type', u'VariableDeclaration']
[u'body', u'kind', u'var']
[u'init', u'declarations', u'body', u'type', u'Literal']
[u'init', u'declarations', u'body', u'value', 4]
[u'declarations', u'body', u'type', u'VariableDeclarator']
[u'id', u'declarations', u'body', u'type', u'Identifier']
[u'id', u'declarations', u'body', u'name', u'j']
[u'body', u'type', u'VariableDeclaration']
[u'body', u'kind', u'var']
[u'init', u'declarations', u'body', u'operator', u'*']
[u'right', u'init', u'declarations', u'body', u'type', u'Identifier']
[u'right', u'init', u'declarations', u'body', u'name', u'j']
[u'init', u'declarations', u'body', u'type', u'BinaryExpression']
[u'left', u'init', u'declarations', u'body', u'type', u'Identifier']
[u'left', u'init', u'declarations', u'body', u'name', u'i']
[u'declarations', u'body', u'type', u'VariableDeclarator']
[u'id', u'declarations', u'body', u'type', u'Identifier']
[u'id', u'declarations', u'body', u'name', u'answer']
[u'body', u'type', u'VariableDeclaration']
[u'type', u'Program']

Of all the Solutions I am reading this is the easiest and works well :-) Thanks Bryukhanov Valentin — Md. Mohsin, Oct 14 '14 at 00:32
I wanted to also obtain indices in case of list/tuple childs. I achieved this by adding `enumerate` and do something like: `for i, v in enumerate(value): for d in dict_generator(v, pre + [key + f'[{i}]']):` — Thomas Fauskanger, Dec 09 '19 at 13:52
Full: https://hastebin.com/agiguhovuj.cs (it's Python, not C#) — Thomas Fauskanger, Dec 09 '19 at 13:59
it works great. It produces a complete list of paths through the tree. one path per list. mypaths=[*dict_generator(myjson)] for path in mypaths: print(path) — Golden Lion, Feb 05 '21 at 18:21
what if i wanted to do this and put it back together after removing keys or items? — Nathanael Steinhauer, May 19 '21 at 19:40
if there's empty dict (`{}`) as the leef value, the path is not included in the result. is it expected? — Lei Yang, Oct 28 '22 at 08:24
Yes, as I got from the question. It's easy to change if they are required in the result. — Valentin Briukhanov, Oct 29 '22 at 09:02

Hans Then · Answer 2 · 2013-11-05T13:43:44.173

55

If you only need to walk the dictionary, I'd suggest using a recursive walk function that takes a dictionary and then recursively walks through its elements. Something like this:

def walk(node):
    for key, item in node.items():
        if item is a collection:
            walk(item)
        else:
            It is a leaf, do your thing

If you also want to search for elements, or query several elements that pass certain criteria, have a look at the jsonpath module.

edited Nov 05 '13 at 13:43

answered Sep 20 '12 at 06:58

Hans Then

10,935
3
32
51

14

This only works for directly nested dictionaries. In the example data structure, there were several dictionary values that were lists of other dictionaries. Some extra logic will be required to handle those (such as recursing inside a list comprehension or generator expression). To make things work right, you probably need to use your knowledge of the meaning of the data, such as the fact that all the dictionaries have a "type" key. – Blckknght Sep 20 '12 at 23:14
1

You should also be careful to check for cycles. e.g.: foo = {}; foo['bar'] = foo will blow you up. Your walk function should keep a list of, and not descend, objects it has seen. (you could pass the list to each successive call) – Cory Mar 25 '15 at 07:18
1

if item is a collection throws an error. what is your import statement – Golden Lion Feb 05 '21 at 18:26

score 10 · Answer 3 · answered Jan 23 '13 at 09:12

Instead of writing your own parser, depending on the task, you could extend encoders and decoders from the standard library json module.

I recommend this especially if you need to encode objects belonging to custom classes into the json. If you have to do some operation which could be done also on a string representation of the json, consider also iterating JSONEncoder().iterencode

For both the reference is http://docs.python.org/2/library/json.html#encoders-and-decoders

score 7 · Answer 4 · answered Sep 20 '12 at 07:53

If you know the meaning of the data, you might want to create a parse function to turn the nested containers into a tree of objects of custom types. You'd then use methods of those custom objects to do whatever you need to do with the data.

For your example data structure, you might create Program, VariableDeclaration, VariableDeclarator, Identifier, Literal and BinaryExpression classes, then use something like this for your parser:

def parse(d):
    t = d[u"type"]

    if t == u"Program":
        body = [parse(block) for block in d[u"body"]]
        return Program(body)

    else if t == u"VariableDeclaration":
        kind = d[u"kind"]
        declarations = [parse(declaration) for declaration in d[u"declarations"]]
        return VariableDeclaration(kind, declarations)

    else if t == u"VariableDeclarator":
        id = parse(d[u"id"])
        init = parse(d[u"init"])
        return VariableDeclarator(id, init)

    else if t == u"Identifier":
        return Identifier(d[u"name"])

    else if t == u"Literal":
        return Literal(d[u"value"])

    else if t == u"BinaryExpression":
        operator = d[u"operator"]
        left = parse(d[u"left"])
        right = parse(d[u"right"])
        return BinaryExpression(operator, left, right)

    else:
        raise ValueError("Invalid data structure.")

Fabiano Silos · Answer 5 · 2016-04-10T16:25:48.110

Maybe can help:

def walk(d):
    global path
      for k,v in d.items():
          if isinstance(v, str) or isinstance(v, int) or isinstance(v, float):
            path.append(k)
            print "{}={}".format(".".join(path), v)
            path.pop()
          elif v is None:
            path.append(k)
            ## do something special
            path.pop()
          elif isinstance(v, dict):
            path.append(k)
            walk(v)
            path.pop()
          else:
            print "###Type {} not recognized: {}.{}={}".format(type(v), ".".join(path),k, v)

mydict = {'Other': {'Stuff': {'Here': {'Key': 'Value'}}}, 'root1': {'address': {'country': 'Brazil', 'city': 'Sao', 'x': 'Pinheiros'}, 'surname': 'Fabiano', 'name': 'Silos', 'height': 1.9}, 'root2': {'address': {'country': 'Brazil', 'detail': {'neighbourhood': 'Central'}, 'city': 'Recife'}, 'surname': 'My', 'name': 'Friend', 'height': 1.78}}

path = []
walk(mydict)

Will produce output like this:

Other.Stuff.Here.Key=Value 
root1.height=1.9 
root1.surname=Fabiano 
root1.name=Silos 
root1.address.country=Brazil 
root1.address.x=Pinheiros 
root1.address.city=Sao 
root2.height=1.78 
root2.surname=My 
root2.name=Friend 
root2.address.country=Brazil 
root2.address.detail.neighbourhood=Central 
root2.address.city=Recife

score 6 · Answer 6 · answered Dec 26 '21 at 22:12

To walk/map over an entire JSON structure, you can use the following code:

def walk(node, key):
    if type(node) is dict:
        return {k: walk(v, k) for k, v in node.items()}
    elif type(node) is list:
        return [walk(x, key) for x in node]
    else:
        return YourFunction(node, key)

def YourFunction(node, key):
    if key == "yourTargetField":   # for example, you want to modify yourTargetField
        return "Modified Value"
    return node # return existing value

This will go through your entire json structure and run every leaf (endpoint key-value pair) through your function. Yourfunction returns the modified value. The entire walk function will give you a new, processed object, in order.

score 4 · Answer 7 · answered Dec 05 '19 at 01:39

If the accepted answer works for you, but you'd also like a full, ordered path with the numerical index of the nested arrays included, this slight variation will work:

def dict_generator(indict, pre=None):
    pre = pre[:] if pre else []
    if isinstance(indict, dict):
        for key, value in indict.items():
            if isinstance(value, dict):
                for d in dict_generator(value,  pre + [key]):
                    yield d
            elif isinstance(value, list) or isinstance(value, tuple):
                for k,v in enumerate(value):
                    for d in dict_generator(v, pre + [key] + [k]):
                        yield d
            else:
                yield pre + [key, value]
    else:
        yield indict

guoyongzhi · Answer 8 · 2021-04-23T08:33:29.803

My more flexible version is as follows:

def walktree(tree, at=lambda node: not isinstance(node, dict), prefix=(), 
                flattennode=lambda node:isinstance(node, (list, tuple, set))):
    """
    Traverse a tree, and return a iterator of the paths from the root nodes to the leaf nodes.
    tree: like '{'a':{'b':1,'c':2}}'
    at: a bool function or a int indicates levels num to go down. walktree(tree, at=1) equivalent to tree.items()
    flattennode: a bool function to decide whether to iterate at node value
    """
    if isinstance(at, int):
        isleaf_ = at == 0
        isleaf = lambda v: isleaf_
        at = at - 1
    else:
        isleaf = at
    if isleaf(tree):
        if not flattennode(tree):
            yield (*prefix, tree)
        else:
            for v in tree:
                yield from walktree(v, at, prefix, flattennode=flattennode)
    else:
        for k,v in tree.items():
            yield from walktree(v, at, (*prefix, k), flattennode=flattennode)

usage:

> list(walktree({'a':{'b':[0,1],'c':2}, 'd':3}))
[('a', 'b', 0), ('a', 'b', 1), ('a', 'c', 2), ('d', 3)]
> list(walktree({'a':{'b':[0,1],'c':2}, 'd':3}, flattennode=lambda e:False))
[('a', 'b', [0, 1]), ('a', 'c', 2), ('d', 3)]
> list(walktree({'a':{'b':[0,1],'c':2}, 'd':3}, at=1))
[('a', {'b': [0, 1], 'c': 2}), ('d', 3)]
> list(walktree({'a':{'b':[0,{1:9,9:1}],'c':2}, 'd':3}))
[('a', 'b', 0), ('a', 'b', 1, 9), ('a', 'b', 9, 1), ('a', 'c', 2), ('d', 3)]
> list(walktree([1,2,3,[4,5]]))
[(1,), (2,), (3,), (4,), (5,)]

please consifer avoiding to post long answers that contains alot of code — Khaled, Apr 23 '21 at 07:57
@Khaled size of code, looks to me like the code is minimal for what is needed — Eduard Florinescu, Apr 24 '21 at 07:16
This needs a blog post to explain it fully. I would actually love that — Christopher Rucinski, Dec 26 '22 at 18:39

score 3 · Answer 9 · answered Jan 02 '19 at 03:49

Some addition to solution above (to handle json including lists)

#!/usr/bin/env python

import json

def walk(d):
   global path
   for k,v in d.items():
      if isinstance(v, str) or isinstance(v, int) or isinstance(v, float):
         path.append(k)
         print("{}={}".format(".".join(path), v)) 
         path.pop()
      elif v is None:
         path.append(k)
         # do something special
         path.pop()
      elif isinstance(v, list):
         path.append(k)
         for v_int in v:
            walk(v_int)
         path.pop()
      elif isinstance(v, dict):
         path.append(k)
         walk(v)
         path.pop()
      else:
         print("###Type {} not recognized: {}.{}={}".format(type(v), ".".join(path),k, v))

with open('abc.json') as f:
   myjson = json.load(f)

path = []
walk(myjson)

score 3 · Answer 10 · answered Aug 20 '22 at 21:06

A bit improved version of the accepted solution. If you're using Python3 (I hope you do) you can use yield from syntax that was introduced in Python 3.3. Also, isinstance as a second argument can accept tuple:

def dict_generator(adict, pre=None):
    pre = pre[:] if pre else []
    if isinstance(adict, dict):
        for key, value in adict.items():
            if isinstance(value, dict):
                yield from dict_generator(value, pre + [key])
            elif isinstance(value, (list, tuple)):
                for v in value:
                    yield from dict_generator(v, pre + [key])
            else:
                yield pre + [key, value]
    else:
        yield pre + [adict]

Iterative version (pretty similar if you're using generators):

def flatten(adict):
    stack = [[adict, []]]
    while stack:
        d, pre = stack.pop()
        if isinstance(d, dict):
            for key, value in d.items():
                if isinstance(value, dict):
                    stack.append([value, pre + [key]])
                elif isinstance(value, (list, tuple)):
                    for v in value:
                        stack.append([v, pre + [key]])
                else:
                    print(pre + [key, value])
        else:
            print(pre + [d])

How to completely traverse a complex dictionary of unknown depth?

10 Answers10

Linked