Python DFS nested dictionary

May 22, 2022

I’ve written a function which should be able to search a nested dictionary, using DFS, to find a specific value. The recursive element seems to be working fine, however, when the base case should return True, it simply doesn’t.

obj = {'a': [{'c':'d'}, {'e':'f'}],
       'b': [{'g':'h'}, {'i':'j'}]}

def obj_dfs(obj, target):
  
  if type(obj) == dict:
    for key, val in obj.items():
      obj_dfs(key, target)
      obj_dfs(val, target) 
  
  elif type(obj) in (list, tuple):
    for elem in obj:
      obj_dfs(elem, target)
  else:
    if obj == target:
      print(f"{obj} == {target}")
      return True
    else:
      print(f"{obj} != {target}")  
  return False 

obj_dfs(obj, 'j')

And the results. As you can see, the standard output "i==i" shows that this element was evaluated correctly but the return True statement isn’t functioning as intended. I’ve verified that if I call obj_dfs(obj, 'j'), that experiences the same error.

a != j
c != j
d != j
e != j
f != j
b != j
g != j
h != j
i != j
j == j
False

Why is this? And how can I fix this?

>Solution :

As the comments point out, you need to return the results of the recursive calls. Since you are just looking for a True/False match, you can pass the recursive calls into any() which will exit early with True if there is a match. The base case can simple be whether obj == target.

obj = {'a': [{'c':'d'}, {'e':'f'}],
       'b': [{'g':'h'}, {'i':'j'}]}

def obj_dfs(obj, target):
    if obj == target:
        return True

    if isinstance(obj, dict):
        return any(obj_dfs(v, target) for v in obj.items())
    
    elif isinstance(obj, (list, tuple)):
        return any(obj_dfs(l, target) for l in obj)

    return False
                   
obj_dfs(obj, 'i'), obj_dfs(obj, 'j'), obj_dfs(obj, 'd'), obj_dfs(obj, 'x')
# (True, True, True, False)

This allows for a three simple blocks. Notice we are checking for a tuple as well as a list in the last isinstance. This allows you to simply pass in the dict item()s rather than looping over keys and values independently.

Adding a print(obj) as the first line of the function will show the order in which you are traversing the data. For example obj_dfs(obj, 'j') will print:

{'a': [{'c': 'd'}, {'e': 'f'}], 'b': [{'g': 'h'}, {'i': 'j'}]}
('a', [{'c': 'd'}, {'e': 'f'}])
a
[{'c': 'd'}, {'e': 'f'}]
{'c': 'd'}
('c', 'd')
c
d
{'e': 'f'}
('e', 'f')
e
f
('b', [{'g': 'h'}, {'i': 'j'}])
b
[{'g': 'h'}, {'i': 'j'}]
{'g': 'h'}
('g', 'h')
g
h
{'i': 'j'}
('i', 'j')
i
j