How to find the maximum "depth" of a python dictionary or JSON object?

Question

I have a json string and I want to know what its maximum depth is. By depth I mean the number of embedded keys. So if one key as 7 "children" and know other key had that many, the depth would be 8.

Since the only types (I believe) that can embed other objects are arrays and other dictionaries that is all that would need to be checked. Is there a way to check this?

I was hoping to achieve this without external modules but if not I am targeting python3.

NOTE: Here is what I mean by "depth"

The following dictionary:

{
  "path": "/0001_Anthem",
  "name": "0001_Anthem",
  "isMovie": true,
  "runtime": 3600,
  "thumbnailLocation": "/thubs/test.png",
  "id": 1, 
  "media": [
    {
      "path": "/0001_Anthem/louvers.mp4",
      "name": "louvers.mp4"
    }
  ]
}

Would have a "depth" or length of 3 because the farthest embedded item is the key/value pair (level 3) in the media array (level 2), in the main dictionary (level 1). I am not sure what terminology others use, this is just the terminology I think make sense.

Thanks

Can you explain what you mean by depth in more detail? It doesn't sound like the usual definition. Maybe some examples? — Blorgbeard
– Blorgbeard, Commented Jun 19, 2015 at 1:07
Are you possibly pointing to collections.Mapping and collections.Sequence if you say "arrays and dicts"? — WorldSEnder
– WorldSEnder, Commented Jun 19, 2015 at 1:12
OK, that actually is the usual definition, I was just confused by your wording :) — Blorgbeard
– Blorgbeard, Commented Jun 19, 2015 at 1:33

Blorgbeard · Accepted Answer · 2015-06-19 01:48:06Z

13

Here's one implementation:

def depth(x):
    if type(x) is dict and x:
        return 1 + max(depth(x[a]) for a in x)
    if type(x) is list and x:
        return 1 + max(depth(a) for a in x)
    return 0

answered Jun 19, 2015 at 1:48

Blorgbeard

104k50 gold badges237 silver badges276 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

jayprakashstar Over a year ago

Doesn't work test this

{'children': [{'name': 'product service',    'children': [{'name': 'price', 'children': [{'name': 'cost', 'size': 8}]},     {'name': 'quality', 'children': [{'name': 'messaging', 'size': 4}]}]},   {'name': 'customer service',    'children': [{'name': 'Personnel',      'children': [{'name': 'CEO', 'size': 7}]}]},   {'name': 'product',    'children': [{'name': 'Apple',      'children': [{'name': 'iPhone 4', 'size': 10}]}]}]}

Ricardo Over a year ago

@jayprakashstar, could you please explain why is it that you think it doesn't work? According to @Startec's original question and definition, your example is depth 7. If you pretty-print your example, you'll see that the max indent level (all keys name and size) is precisely 7.

Pete Cacioppi · Accepted Answer · 2015-06-19 01:47:06Z

1

def depth(d):
    if hasattr(d, "values"):
        return 1 + max(map(depth, d.values()))
    if hasattr(d, "__len__") and not hasattr(d, "lower"):
        return 1 + max(map(depth, d))
    return 0

answered Jun 19, 2015 at 1:47

Pete Cacioppi

9408 silver badges13 bronze badges

Comments

NeoWang · Accepted Answer · 2015-06-19 02:41:34Z

Taking a closer look at your Q, you want to get the depth from a JSON string. Here is a function I write:

# This function count list/dict/tuple as levels
def get_json_depth(s):
    d = {"(":")", "[":"]", "{":"}" }
    stack = []
    lefts = d.keys()
    rights = d.values()

    max_depth = 0
    depth = 0
    in_quotes = False

    for c in s:
            if c == '"':
                    in_quotes = not in_quotes
            if not in_quotes:
                    if c in lefts:
                            stack.append(c)
                            depth += 1
                            if depth > max_depth:
                                    max_depth = depth
                    elif c in rights:
                            if not stack:
                                    raise Exception()
                            if c != d[stack.pop()]:
                                    raise Exception()
    return max_depth

But if you don't mind using json.loads(s) to convert it to dictionary, then use @Blorgbeard's recursive function.

Jenner Felton · Accepted Answer · 2015-06-19 01:10:02Z

0

You can find the depth using a recursive function like so.

def depth(jsnFile):
    if jsnFile.has_key('children'):
       return 1 +  max([0] + map(depth, jsnFile['children']))
    else:
       return 1

answered Jun 19, 2015 at 1:10

Jenner Felton

8171 gold badge10 silver badges18 bronze badges

1 Comment

Startec Over a year ago

I meant for a dictionary with unknown key names (where even the key names are not known)

Collectives™ on Stack Overflow

How to find the maximum "depth" of a python dictionary or JSON object?

4 Answers 4

2 Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related