Recursively iterate through a nested dict and return value of the first matching key


I have a deeply nested dict and need to iterate through it and return the value corresponding to the key argument, second argument of my function.

For example, with

tree = {"a": 12, "g":{ "b": 2, "c": 4}, "d":5}

tree_traverse(tree, "d") should return 5

Here is my code:

def tree_traverse(tree, key): for k,v in tree.items(): if isinstance(v, dict): tree_traverse(v, key) elif k == key: return v

The problem I have is that this function returns None if it doesnt find the matching key once it's done iterating through the deepest nested dict. I don't want it to return anything before the matching key is found.

I didn't find a solution in another thread, most of them use print statements and don't return anything so I guess it avoids this issue.


You have to check whether the recursive call actually found something so you can continue the loop. E.g. try the following:

def tree_traverse(tree, key): for k, v in tree.items(): if k == key: return v elif isinstance(v, dict): found = tree_traverse(v, key) if found is not None: # check if recursive call found it return found

Here we instantiate an object when the function is created, that all executions of the function will share, called _marker. We return this object if we don't find the key. (You could also use None here, but None is frequently a meaningful value.)

def tree_traverse(tree, key, *, _marker=object()): for k,v in tree.items(): if isinstance(v, dict): res = tree_traverse(v, key, _marker=_marker) if res is not _marker: return res elif k == key: return v return _marker def find(tree, key): _marker = object() res = tree_traverse(tree, key, _marker=_marker) if res is _marker: raise KeyError("Key {} not found".format(key)) return res

I use tree_traverse as a helper function because we want different behaviour at the outermost layer of our recursion (throw an error) than we want inside (return a _marker object)



  • handle links clicking inside PDF viewer on iOS with swift
  • how to get total count of number of employees according to level
  • Column contains column 1
  • Haskell package vector-space fails at compile time
  • Extraction of common element in given arrays to make a new array
  • Node js adding unwanted modules when I do npm install [duplicate]
  • SOAPpy - reserved word in named parameter list
  • Compare two table and find matching columns
  • Slf4j with Log4j does not print wrapped exception (caused by) when wrapper exception has a message
  • Wordpress form with file upload submit with Ajax
  • How to find the character after second vowel in a string
  • Should authentication be in a separate service for wcf?
  • Running Applescript from a Cocoa application
  • FMX: dropping selfmade component on form duplicates subcomponents
  • Images tile on Google map in android
  • Eclipse (ctrl+space) content assist hook
  • execute .sql file using command line
  • 3 transitions, pausetime between transitions
  • Python C binding error
  • connect.cookieParser and connect.session
  • Why am I getting an Argument exception when creating event handler dynamically?
  • How to load dynamic images in custom ListView
  • What is the difference between dynamically creating a script tag and statically embed a script tag?
  • Year over Year Stats from a Crossfilter Dataset
  • Neo4j…how to get a visual representation of my data?
  • Another “Cannot make static reference…” Question
  • Spring Boot fails to start
  • Make checkout phone field optional for specific countries in WooCommerce
  • calling IO Operations from thread in ruby c extension will cause ruby to hang
  • Angular 4: Responsive Grid List
  • Firebase: How to read from external DB?
  • Write to .csv file with PHP (Commas in Data Error)
  • How to mutate multiple variables without repeating codes?
  • How to check if object is null in Java?