n-depth tree: set parent value based on children values

Question

In a n-depth dict where values are set in the deepest level of a hierarchy:

{
    "name": "root",
    "value": None, # expected value to be 80
    "children": [
        {
            "name": "a",
            "value": None, # expected value to be 30
            "children": [
                { "name": "a.1", "value": 10 },
                { "name": "a.2", "value": 20 }
            ]
        },
        {
            "name": "b",
            "value": None, # expected value to be 50
            "children": [
                { "name": "b.1", "value": 25 },
                {
                    "name": "b.2",
                    "value": None, # expected value to be 25
                    "children": [
                        {"name": "b.2.1", "value": 5},
                        {"name": "b.2.2", "value": 5},
                        {"name": "b.2.3", "value": 5},
                        {"name": "b.2.4", "value": 5},
                        {"name": "b.2.5", "value": 5}
                    ]
                }
            ]
        }
    ]
}

What could be the approach to recursively set each parent value based on the result of an operation perfomed with its children value (i.e. sum)?

Answer 1

I finally managed to do it using the iterative level order traversal pattern (BFS), I was missing just a couple of details.

This approach works because the depth iteration order is guaranteed, so once we are getting to a node wich has children, all its sub-level children are already calculated.

The solution:

def reverseTraversal(obj):

    def parentOperation(node):
        out = 0
        for child in node['children']:
            out = out + child['value']
        return out

    if obj is None:
        return
    queue = []
    stack = []
    queue.append(obj)
    while len(queue) > 0:
        temp = queue.pop(0)
        stack.append(temp)
        if 'children' in temp and len(temp['children']) > 0:
            for child in temp['children']:
                queue.append(child)

    while len(stack)>0:
        node = stack.pop()
        if 'children' in node and len(node['children']) > 0:
            node['value'] = parentOperation(node)

# obj is the original dict
obj = reverseTraversal(obj)
print(obj)

Results in:

{
  "name": "root",
  "value": 80,
  "children": [
    {
      "name": "a",
      "value": 30,
      "children": [
        {"name": "a.1","value": 10},
        {"name": "a.2","value": 20}
      ]
    },
    {
      "name": "b",
      "value": 50,
      "children": [
        {"name": "b.1","value": 25},
        {
          "name": "b.2",
          "value": 25,
          "children": [
            {"name": "b.2.1","value": 5},
            {"name": "b.2.2","value": 5},
            {"name": "b.2.3","value": 5},
            {"name": "b.2.4","value": 5},
            {"name": "b.2.5","value": 5}
          ]
        }
      ]
    }
  ]
}

Answer 2

Given your datastructure and a list of values to update, you can use next in recursion:

def update(d, targets):
   return {a:[update(i, targets) for i in b] if isinstance(b, list) else update(b, targets) if isinstance(b, dict) else next(targets) if not b else b for a, b in d.items()}

targets = [80, 30, 50, 25]
results = update(nlist, iter(targets))

Output:

{'children': [{'children': [{'name': 'a.1', 'value': 10},
                        {'name': 'a.2', 'value': 20}],
           'name': 'a',
           'value': 30},
          {'children': [{'name': 'b.1', 'value': 25},
                        {'children': [{'name': 'b.2.1', 'value': 5},
                                      {'name': 'b.2.2', 'value': 5},
                                      {'name': 'b.2.3', 'value': 5},
                                      {'name': 'b.2.4', 'value': 5},
                                      {'name': 'b.2.5', 'value': 5}],
                         'name': 'b.2',
                         'value': 25}],
           'name': 'b',
           'value': 50}],
 'name': 'root',
 'value': 80}