skip to Main Content

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 }
];

2

Answers


  1. 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. 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