Reason About Recursive Key Search in Nested JSON

Problem Statement

In document databases like MongoDB, documents can contain arbitrarily nested structures consisting of nested objects (maps/dictionaries) and arrays (lists).

Write a function find_values(document, target_key) that recursively traverses a nested JSON document and collects all values associated with target_key.

Your implementation must adhere to the following rules:

• If an object contains target_key, append its associated value to the results. If that associated value is itself a nested dictionary or list, you should still search inside it for further occurrences of target_key.
• If a list/array is encountered, recursively inspect each element in order.
• If the target key appears multiple times across different branches or nesting depths, preserve pre-order depth-first traversal order in the returned list.
• If the key is not present anywhere in the document, return an empty list [].
• Keys are case-sensitive.

Function Signature

from typing import Any

def find_values(document: Any, target_key: str) -> list[Any]:
    pass

Examples

Example 1

input_doc = {
    "user": {
        "id": 101,
        "name": "Alice",
        "metadata": {
            "id": "sub_101",
            "status": "active"
        }
    },
    "tags": ["admin", "staff"],
    "id": 999
}
target = "id"

# Output:
# [101, "sub_101", 999] (or [999, 101, "sub_101"] depending on dict key ordering; pre-order traversal of keys)

Explanation: The key "id" appears at the root level (999), under "user" (101), and under "metadata" ("sub_101"). All three values are collected.

Example 2

input_doc = {
    "item": {
        "item": {
            "name": "Widget"
        }
    }
}
target = "item"

# Output:
# [{"item": {"name": "Widget"}}, {"name": "Widget"}]

Explanation: The outer "item" maps to a dict that itself contains another "item" key. Both values are captured.

Constraints

• The document structure contains only valid JSON types: dict, list, str, int, float, bool, and None.
• Nesting depth will not exceed 500 levels.
• Total number of keys and array elements across the document is at most 10^5.

Edge Cases

• The target value itself is None or an empty container ({} or []).
• The root input is an empty dictionary, an empty list, or a primitive value.
• Multiple identical values or duplicated keys across branches.