Question 204331 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – 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 }
];
Tags:

2

Answers


  1. 0

    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.
    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));
    Login or Signup to reply.
  2. 0

    If only leaf nodes contain total:

    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 total
    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)));

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

    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 = {};

for (const item of arr) {
    map[item.id] = item;
}

// find parent IDs to filter leaf nodes
const parentIds = new Set(arr.map(item => 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 its total
    // if the total isn't updated (touched) yet, init it
    let parent = item;
    while (parent = map[parent.parent_id]) {
        'total' in parent && touchedParents.has(parent) ? parent.total += item.total : touchedParents.add(parent) && (parent.total = item.total);
    }

}

arr.forEach(item => console.log(JSON.stringify(item)));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search