Return Root To Specific Leaf From A Nested Dictionary Tree

The nested dictionary tree is of the form, categories = [{ 'name': 'Cat1', 'children': [{ 'name': 'SubCat1', 'children': [{ 'name': 'SubSubCat1'

Solution 1:

Don't pass along a list; it'll accumulate all searched paths, not just the one that matches. Build up the list as you recurse, by concatenating. You also need to process the result of the recursive call; your code ignores that result.

The following works, note that when we recurse (in if category['children']) the code has to check if a path was found in that subtree:

defrecurse_category(categories, to_find):
    for category in categories:
        if category['name'] == to_find:
            returnTrue, [category['name']]
        if category['children']:
            found, path = recurse_category(category['children'], to_find)
            if found:
                returnTrue, [category['name']] + path
    returnFalse, []

This returns a boolean (true if found) and the path:

>>> recurse_category(categories, 'SubCat1')
(True, ['Cat1', 'SubCat1'])
>>> recurse_category(categories, 'Cat2')
(True, ['Cat2'])
>>> recurse_category(categories, 'Nonesuch')
(False, [])