How to calculate the sum of the children in a general tree using Javascript

user_8466281 0
Viewed 1639

enter image description here

I want to calculate the sum of the child nodes and save that on parent node. As showed in image blue numbers are sum of children.

I have tried this so far: 

    const tree = {
          name:"Root Node",
          value:0,
          sumOfTheChildren:0,
          children: [
              {

                 name:"A Node",
                 value:10,
                 sumOfTheChildren:0,
                 children:[]
              },

              {

                 name:"B Node",
                 value:10,
                 sumOfTheChildren:0,
                 children:[]
              }

    ]

    }

and so on ....

So in sumOfTheChildren of every node i want calculate sum of the children (all descendant nodes)

so i am trying to do post-order tree traversal like this. 

let sum = 0;
function postOrder(root) {
  if (root == null) return;

  root.children.forEach((el) =>{
     postOrder(el);

  });

  sum+=root.value;

  // Here i am not sure how to do this 
  root.sumOfTheChildren+=root.value;

}

postOrder(tree);

But this is not giving required result. So How do i get proper sum?

tree depth-first-search algorithm javascript
1 Answers

The logic can be simplified by recursively calculating the children's sum first, and then returning the sum of the children values and the parents value.

const tree = {
  name: "Root Node",
  value: 0,
  sumOfTheChildren: 0,
  children: [{

      name: "A Node",
      value: 10,
      sumOfTheChildren: 0,
      children: [{

        name: "D Node",
        value: 35,
        sumOfTheChildren: 0,
        children: []
      }]
    },

    {

      name: "B Node",
      value: 10,
      sumOfTheChildren: 0,
      children: []
    }

  ]
};

function postOrder(root) {
  if (root.children) {
    root.children.forEach(child => {
      root.sumOfTheChildren += postOrder(child);
    });
  }

  return root.sumOfTheChildren + root.value;
}

console.log(postOrder(tree));
console.log(tree);

user_15861740
Related