Get "path" of parent keys and indices in dictionary of nested dictionaries and lists

Question

I am receiving a large json from Google Assistant and I want to retrieve some specific details from it. The json is the following:

{
    "responseId": "************************",
    "queryResult": {
        "queryText": "actions_intent_DELIVERY_ADDRESS",
        "action": "delivery",
        "parameters": {},
        "allRequiredParamsPresent": true,
        "fulfillmentMessages": [
            {
                "text": {
                    "text": [
                        ""
                    ]
                }
            }
        ],
        "outputContexts": [
            {
                "name": "************************/agent/sessions/1527070836044/contexts/actions_capability_screen_output"
            },
            {
                "name": "************************/agent/sessions/1527070836044/contexts/more",
                "parameters": {
                    "polar": "no",
                    "polar.original": "No",
                    "cardinal": 2,
                    "cardinal.original": "2"
                }
            },
            {
                "name": "************************/agent/sessions/1527070836044/contexts/actions_capability_audio_output"
            },
            {
                "name": "************************/agent/sessions/1527070836044/contexts/actions_capability_media_response_audio"
            },
            {
                "name": "************************/agent/sessions/1527070836044/contexts/actions_intent_delivery_address",
                "parameters": {
                    "DELIVERY_ADDRESS_VALUE": {
                        "userDecision": "ACCEPTED",
                        "@type": "type.googleapis.com/google.actions.v2.DeliveryAddressValue",
                        "location": {
                            "postalAddress": {
                                "regionCode": "US",
                                "recipients": [
                                    "Amazon"
                                ],
                                "postalCode": "NY 10001",
                                "locality": "New York",
                                "addressLines": [
                                    "450 West 33rd Street"
                                ]
                            },
                            "phoneNumber": "+1 206-266-2992"
                        }
                    }
                }
            },
            {
                "name": "************************/agent/sessions/1527070836044/contexts/actions_capability_web_browser"
            }
        ],
        "intent": {
            "name": "************************/agent/intents/86fb2293-7ae9-4bed-adeb-6dfe8797e5ff",
            "displayName": "Delivery"
        },
        "intentDetectionConfidence": 1,
        "diagnosticInfo": {},
        "languageCode": "en-gb"
    },
    "originalDetectIntentRequest": {
        "source": "google",
        "version": "2",
        "payload": {
            "isInSandbox": true,
            "surface": {
                "capabilities": [
                    {
                        "name": "actions.capability.MEDIA_RESPONSE_AUDIO"
                    },
                    {
                        "name": "actions.capability.SCREEN_OUTPUT"
                    },
                    {
                        "name": "actions.capability.AUDIO_OUTPUT"
                    },
                    {
                        "name": "actions.capability.WEB_BROWSER"
                    }
                ]
            },
            "inputs": [
                {
                    "rawInputs": [
                        {
                            "query": "450 West 33rd Street"
                        }
                    ],
                    "arguments": [
                        {
                            "extension": {
                                "userDecision": "ACCEPTED",
                                "@type": "type.googleapis.com/google.actions.v2.DeliveryAddressValue",
                                "location": {
                                    "postalAddress": {
                                        "regionCode": "US",
                                        "recipients": [
                                            "Amazon"
                                        ],
                                        "postalCode": "NY 10001",
                                        "locality": "New York",
                                        "addressLines": [
                                            "450 West 33rd Street"
                                        ]
                                    },
                                    "phoneNumber": "+1 206-266-2992"
                                }
                            },
                            "name": "DELIVERY_ADDRESS_VALUE"
                        }
                    ],
                    "intent": "actions.intent.DELIVERY_ADDRESS"
                }
            ],
            "user": {
                "lastSeen": "2018-05-23T10:20:25Z",
                "locale": "en-GB",
                "userId": "************************"
            },
            "conversation": {
                "conversationId": "************************",
                "type": "ACTIVE",
                "conversationToken": "[\"more\"]"
            },
            "availableSurfaces": [
                {
                    "capabilities": [
                        {
                            "name": "actions.capability.SCREEN_OUTPUT"
                        },
                        {
                            "name": "actions.capability.AUDIO_OUTPUT"
                        },
                        {
                            "name": "actions.capability.WEB_BROWSER"
                        }
                    ]
                }
            ]
        }
    },
    "session": "************************/agent/sessions/1527070836044"
}

This large json returns amongst other things to my back-end the delivery address details of the user (here I use Amazon's NY locations details as an example). Therefore, I want to retrieve the location dictionary which is near the end of this large json. The location details appear also near the start of this json but I want to retrieve specifically the second location dictionary which is near the end of this large json.

For this reason, I had to read through this json by myself and manually test some possible "paths" of the location dictionary within this large json to find out finally that I had to write the following line to retrieve the second location dictionary:

location = json['originalDetectIntentRequest']['payload']['inputs'][0]['arguments'][0]['extension']['location']

Therefore, my question is the following: is there any concise way to retrieve automatically the "path" of the parent keys and indices of the second location dictionary within this large json?

Hence, I expect that the general format of the output from a function which does this for all the occurrences of the location dictionary in any json will be the following:

[["path" of first `location` dictionary], ["path" of second `location` dictionary], ["path" of third `location` dictionary], ...]

where for the json above it will be

[["path" of first `location` dictionary], ["path" of second `location` dictionary]]

as there are two occurrences of the location dictionary with

["path" of second `location` dictionary] = ['originalDetectIntentRequest', 'payload', 'inputs', 0, 'arguments', 0, 'extension', 'location']

I have in my mind relevant posts on StackOverflow (Python--Finding Parent Keys for a specific value in a nested dictionary) but I am not sure that these apply exactly to my problem since these are for parent keys in nested dictionaries whereas here I am talking about the parent keys and indices in dictionary with nested dictionaries and lists.

Answer 1

I solved this by using recursive search

# result and path should be outside of the scope of find_path to persist values during recursive calls to the function
result = []
path = []
from copy import copy

# i is the index of the list that dict_obj is part of
def find_path(dict_obj,key,i=None):
    for k,v in dict_obj.items():
        # add key to path
        path.append(k)
        if isinstance(v,dict):
            # continue searching
            find_path(v, key,i)
        if isinstance(v,list):
            # search through list of dictionaries
            for i,item in enumerate(v):
                # add the index of list that item dict is part of, to path
                path.append(i)
                if isinstance(item,dict):
                    # continue searching in item dict
                    find_path(item, key,i)
                # if reached here, the last added index was incorrect, so removed
                path.pop()
        if k == key:
            # add path to our result
            result.append(copy(path))
        # remove the key added in the first line
        if path != []:
            path.pop()

# default starting index is set to None
find_path(di,"location")
print(result)
# [['queryResult', 'outputContexts', 4, 'parameters', 'DELIVERY_ADDRESS_VALUE', 'location'], ['originalDetectIntentRequest', 'payload', 'inputs', 0, 'arguments', 0, 'extension', 'location']]