Sum all value in a tree data

Here is the input arr:

const  arr = [
  { id: 1 },
  { id: 11, parent_id: 1, total: 2 },
  { id: 12, parent_id: 1 },
  { id: 121, parent_id: 12, total: 1 },
  { id: 122, parent_id: 12, total: 2 }
];

I need to format the arrays. Use recursive function, the value of "total" in parent node = sum all the value of "total" in childs node. The expected output will be:

[
  { id: 1 , total: 5}, 
  { id: 11, parent_id: 1, total: 2 },
  { id: 12, parent_id: 1, total: 3 }, 
  { id: 121, parent_id: 12, total: 1 },
  { id: 122, parent_id: 12, total: 2 }
];

ok so for this you need to consider following things:

1. first find out all nodes that are parent nodes.
2. for each parent node, you need to sum the total values of its child nodes.
3. if a child node doesn't have a total value, then its total is the sum of its own child nodes.
4. if a node doesn't have a total and also doesn't have any child nodes, then it doesn't contribute to the total of its parent node.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function sumTree(arr) {
let map = {};
let root;
// Create nodes map and find root
for(let obj of arr) {
map[obj.id] = {...obj, total: obj.total || 0, children: []};
if(!obj.parent_id) root = map[obj.id];
}
// Build tree
for(let obj of arr) {
if(obj.parent_id) {
map[obj.parent_id].children.push(map[obj.id]);
}
}
// Function to calculate total recursively
function calculateTotal(node) {
for(let child of node.children) {
calculateTotal(child);
node.total += child.total;
}
}
calculateTotal(root);
// Function to convert the tree back to an array
function flattenTree(node) {
let res = [];
for(let child of node.children) {
res = res.concat(flattenTree(child));
}
return [{id: node.id, parent_id: node.parent_id, total: node.total}].concat(res);
}
return flattenTree(root);
}
const arr = [
{ id: 1 },
{ id: 11, parent_id: 1, total: 2 },
{ id: 12, parent_id: 1 },
{ id: 121, parent_id: 12, total: 1 },
{ id: 122, parent_id: 12, total: 2 }
];
console.log(sumTree(arr));

<!-- end snippet -->

If only leaf nodes contain total:

<!-- begin snippet: js hide: true console: true babel: false -->

<!-- language: lang-js -->

const arr = [
{ id: 1 },
{ id: 11, parent_id: 1, total: 2 },
{ id: 12, parent_id: 1 },
{ id: 121, parent_id: 12, total: 1 },
{ id: 122, parent_id: 12, total: 2 }
];
// collect items into an array by ID for further tree walking
const map = {};
for (const item of arr) {
map[item.id] = item;
}
// we have totals only in leaf nodes so filter them and iterate
for (const item of arr.filter(item => 'total' in item)) {
// walk through parents of a leaf node and add to their totals
let parent = item;
while (parent = map[parent.parent_id]) {
parent.total = 'total' in parent ? parent.total + item.total : item.total;
}
}
arr.forEach(item => console.log(JSON.stringify(item)));

<!-- end snippet -->

Otherwise find leaf nodes (this is also for updating parents when some leaf is changed):

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

const arr = [
{ id: 1, total: 100 },
{ id: 11, parent_id: 1, total: 2 },
{ id: 12, parent_id: 1, total: 1000 },
{ id: 121, parent_id: 12, total: 1 },
{ id: 122, parent_id: 12, total: 2 }
];
// collect items into an array by ID for further tree walking
const map = {};
// find parent IDs to filter leaf nodes
const parentIds = new Set;
for (const item of arr) {
map[item.id] = item;
parentIds.add(item.parent_id);
}
const touchedParents = new Set;
// we have totals only in leaf nodes so filter them and iterate
for (const item of arr.filter(item => !parentIds.has(item.id))) {
// walk through parents of a leaf node and add to their totals
// if the total isn't updated (touched) yet, init it
let parent = item;
while (parent = map[parent.parent_id]) {
touchedParents.has(parent) ? parent.total += item.total : touchedParents.add(parent) && (parent.total = item.total);
}
}
arr.forEach(item => console.log(JSON.stringify(item)));

<!-- end snippet -->

In my opinion, We should transform it to a tree, This mindset can help us develop a good habit of thinking in terms of data structures

const arr = [
  { id: 1 },
  { id: 11, parent_id: 1, total: 2 },
  { id: 12, parent_id: 1 },
  { id: 121, parent_id: 12, total: 1 },
  { id: 122, parent_id: 12, total: 2 }
];

function buildTree(arr) {
  const tree = [];

  const map = new Map();
  for (const item of arr) {
    map.set(item.id, { ...item, children: [] });
  }

  for (const item of arr) {
    if (item.parent_id) {
      const parent = map.get(item.parent_id);
      if (parent) {
        parent.children.push(map.get(item.id));
      }
    } else {
      tree.push(map.get(item.id));
    }
  }

  const calculateTotal = (node) => {
    let total = node.total || 0;
    for (const child of node.children) {
      total += calculateTotal(child);
    }
    node.total = total;
    return total;
  };

  for (const node of tree) {
    calculateTotal(node);
  }

  return tree;
}

const tree = buildTree(arr);

Then you can use DFS to print out your idea result