CODEWITHSUNDEEP
pythondictionarynested
user3370397
user3370397

Reputation:

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',
            'children': []
         }]
     }]
}, {
    'name': 'Cat2',
    'children': []
}]

The recursive function should return the path from root to a specific leaf.

Lets say, function(categories, 'SubCat1') should return a list containing ['Cat1', 'SubCat1']. Likewise for function(categories, 'Cat2') should return the ['Cat2'].

Progress made so far

def recurse_category(categories, to_find):
    def _recurse_category(categories, to_find, path=[]):
        for category in categories:
            path.append(category['name'])
            if len(category['children']) == 0 and category['name'] != to_find:
                return path, False

            if category['name'] == to_find:
                return path, True
            else:
                recurse_category(
                    category['children'], to_find, path
                )
    return _recurse_category(categories, to_find, path=[])

Upvotes: 0

Views: 382

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1121834

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:

def recurse_category(categories, to_find):
    for category in categories:
        if category['name'] == to_find:
            return True, [category['name']]
        if category['children']:
            found, path = recurse_category(category['children'], to_find)
            if found:
                return True, [category['name']] + path
    return False, []

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, [])

Upvotes: 1

Related Questions