How to implement DFS with recursive function on JSON dict of tree?

Question

I use a recursive Depth-First-Search function to traverse a tree where each node has an index.

During traversing, I need to assign one node (whose type is dict) to a variable to further process from outer scope.

It seems that I use a useless assignment. What is the most efficient way to do that?

def dfs(json_tree, index, result):
    if json_tree['index'] == index:
        result = json_tree['index']   ## not work!
        return
    if 'children' not in json_tree:
        return
    for c in json_tree['children']:
        dfs(c, index, result)

Answer 1

Try returning result instead. Note that I changed your function signature. This will also short-circuit the search as soon as index is found.

def dfs(json_tree, index):
    if json_tree['index'] == index:
        return json_tree['index']
    if 'children' not in json_tree:
        return None
    for c in json_tree['children']:
        result = dfs(c, index)
        if result is not None:
            return result
    return None

Edit: Updated with a final return path in case index is never found.