pythonrecursiontree-structure

Recursive sums in dictionary


i've got a classic tree problem and can't find the right solution. I have a tree represented in a python dictionary with branches and leafes. I need to calculate the sum of all children (price-property) for every branch and store it in the sum-property. Here is a sample of my tree (dict):

[
    {
        "id": 1,
        "type": "group",
        "name": "test-group 1",
        "price": 0,
        "sum": 0,
        "children": [
            {
                "id": 2,
                "type": "position",
                "name": "test-inner 1",
                "price": 5
            },
            {
                "id": 3,
                "type": "position",
                "name": "test-inner 2",
                "price": 10
            }
        ]
    },
    {
        "id": 4,
        "type": "group",
        "name": "test-group 2",
        "sum": 0,
        "children": [
            {
                "id": 5,
                "type": "position",
                "name": "test-inner 3",
                "price": 5
            },
            {
                "id": 6,
                "type": "group",
                "name": "test-group 3",
                "sum": 0,
                "children": [
                    {
                        "id": 7,
                        "type": "position",
                        "name": "test-inner 4",
                        "price": 5
                    },
                    {
                        "id": 8,
                        "type": "position",
                        "name": "test-inner 5",
                        "price": 10
                    }
                ]
            }
        ]
    }
]

I'm sure i need recursion and already found solutions to get the sum of the whole tree...but i need the partial sums too...

Thanks for your help!


Solution

  • You can try somtehing along the following lines:

    def dct_sum(dct):
        if isinstance(dct, dict):
            if 'price' in dct:
                return dct['price']
            if 'children' in dct:
                dct['sum'] = sum(dct_sum(c) for c in dct['children'])
                return dct['sum']
        if isinstance(dct, list):
            return sum(dct_sum(item) for item in dct)
        return 0