Get the sum of property of nested array of objects with infinite depth

Question

I have an array of objects representing something similar to the system's hard-drive folder structure. Data is represented in a nested array of objects. Each object is a folder containing some files and folders. I know exactly the sum of the size of files directly placed in each node. But I don't know how much space a node has taken containing its child nodes.

Here is an example of the data:

[{
    id: 1,
    name: 'root',
    filesSize: 123456,
    children: [{
        id: 2,
        name: 'child 1',
        filesSize: 789654,
      },
      {
        id: 3,
        name: 'child 2',
        filesSize: 321123,
        children: [{
            id: 4,
            name: 'child 3 - 1',
            filesSize: 88888,
          },
          {
            id: 5,
            name: 'child 3 - 2',
            filesSize: 99999,
            children: [{
                id: 99999,
                name: 'child m - n',
                filesSize: ...,
              },
              .
              .
              .
            }]
        }]
    }]

I tried to use Array.reduce, but it doesn't help me because it only iterates on direct children of object - not n level of the nested array. Something like this:

const parentSize = typeof parent['total'] !== 'undefined' ? parent['total'] : parent.filesSize;
parent['total'] = children.reduce((sum, child) => {
    return sum + (typeof child.total !== 'undefined' ? child.filesSize : child.total);
}, parentSize);

What am I missing?

Answer 1

I took the liberty of doubling the objects from top to bottom so it splits at the root four levels deep.

/**@function
 * @Name totalFileSize
 * @Description - This function accepts array of objects and any nested array of 
 * objects as well. It will extract a number value of a given key 
 * and recursively search all sub-arrays as well. It will return the sum of all 
 * extracted values.
 * @param {array<object>} objArr - An array of objects
 * @param {string} prop - A key/property with a number value  
 * @returns {number} - A sum of all extracted number values
 */

Pass the array of objects and the property you want to get the total sum of.

//                data↘️         ↙️"filesSize"
const totalFileSize = (objArr, prop) =>

Next, run each object through .map() and then convert each object into an array of pairs by using Object.entries(). An array of pairs is a 2D array in which the sub-arrays consist of two elements:
[[key, value], [key, value],...]

objArr.map(obj => Object.entries(obj)
// [{A: 1, B: 'z'}, {...},...] => [["A", 1], ["B", "z"], [...],...]

Now we have a 2D array witch is easier to work with using Array methods. The logical choice of methods is .reduce() since we need a single result. The second parameter represents the element of the current iteration, note it is destructured into an array (specifically a key/value pair). In this form we can easily construct more granular expressions.

//          ↙️On each iteration, this value accumulates when a match is made
.reduce((sum, [key, val]) => 
//   property↗️       ↖️value      

The destructured values allow us to write a more terse and direct way. The heart of this function is a if/else if/else statement as a ternary conditional.

/* if the current key matches prop ("filesSize"), then add sum and the current value 
(val).*/
key == prop ? sum + parseInt(val) :
/* Note: the value needed to be converted to a number because the + operator coerced
it into a String.*/

Now onto the 2nd (or else if) of the ternary operator. I noticed there's a running total property in the other answers, so here's where to get it: obj.total = sum + parseInt(totalFileSize(val, prop)). It's the sum and the return value of each recursive call. I don't think the total should be calculated for each object (all you get is a duplicate value of filesSize).

/* else if val is an array recursively invoke totalFileSize() and pass val and 
prop in...*/
Array.isArray(val) ? obj.total = sum + parseInt(totalFileSize(val, prop)) : 
// ...then convert it's return into a number and add it to sum

else add 0 to sum. Any non-matching values are no longer a worry.

0, 0))
// The last zero is the initial value of `.reduce()`

Last thing to do is cleanup the return value. The data was doubled so I can demonstrate the functions ability to handle multiple branches. At this point all numbers from "filesSize" are now two totals in an array. This last step adds all branches together.

.reduce((total, current) => total + current);

const data =[{"id":1,"name":"root","filesSize":123456,"children":[{"id":2,"name":"child 1","filesSize":789654},{"id":3,"name":"child 2","filesSize":321123,"children":[{"id":4,"name":"child 3 - 1","filesSize":88888},{"id":5,"name":"child 3 - 2","filesSize":99999,"children":[{"id":6,"name":"child 4 - 1","filesSize":325941}]}]}]},
{"id":7,"name":"root","filesSize":654321,"children":[{"id":8,"name":"child 1","filesSize":978855},{"id":9,"name":"child 2","filesSize":123321,"children":[{"id":10,"name":"child 3 - 1","filesSize":11111},{"id":11,"name":"child 3 - 2","filesSize":66666,"children":[{"id":12,"name":"child 4 - 1","filesSize":18756}]}]}]}];

const totalFileSize = (objArr, prop) =>
objArr.map(obj => Object.entries(obj)
.reduce((sum, [key, val]) => 
key == prop ? sum + parseInt(val) : 
Array.isArray(val) ?  obj.total = sum + parseInt(totalFileSize(val, prop)) : 
0, 0))
.reduce((total, current) => total + current);

console.log(`Input array is doubled at the root so this the total sum of 12 objects not 6 like OP example.`);
console.log(totalFileSize(data, "filesSize"));
console.log(data);

Answer 2

Just a note:

Assuming your size unit is bytes:

1 petabyte is 1_000_000_000_000_000 bytes (or 1e3 ** 5): so your sum (which is a JS number) can safely hold Number.MAX_SAFE_INTEGER / (1e3 ** 5), which is about 9. If you expect that your size will approach 9 petabytes, you should use a BigInt type to store the sum instead of a number.

The other answers demonstrate recursive approaches, which are terse and elegant, but will fail if your hierarchy is too numerous (stack overflow!).

Here's an iterative alternative:

TS Playground

function getTotal (containerNode) {
  let total = 0;
  const stack = [containerNode];

  while (stack.length > 0) {
    const node = stack.pop();

    // Already available, skip children
    if (typeof node.total === 'number') {
      total += node.total;
      continue;
    }

    total += node.filesSize;
    if (!node.children?.length) continue;
    for (const child of node.children) stack.push(child);
  }

  return total;
}


// Example usage:

const nodes = [
  {
    id: 1,
    name: 'root',
    filesSize: 123456,
    children: [
      {
        id: 2,
        name: 'child 1',
        filesSize: 789654,
      },
      {
        id: 3,
        name: 'child 2',
        filesSize: 321123,
        total: 321123 + 88888 + 99999 + 34523,
        children: [
          {
            id: 4,
            name: 'child 3 - 1',
            filesSize: 88888,
          },
          {
            id: 5,
            name: 'child 3 - 2',
            filesSize: 99999,
            children: [
              {
                id: 99999,
                name: 'child m - n',
                filesSize: 34523,
              },
              // ...
            ],
          },
        ],
      },
    ],
  },
];

function test (containerNode, expectedTotal) {
  const actual = getTotal(containerNode);
  return `${containerNode.id}: ${actual === expectedTotal ? 'pass' : 'fail'}`;
}

const results = [
  test(
    nodes[0].children[1].children[1].children[0],
    34523,
  ),
  test(
    nodes[0].children[1].children[1],
    99999 + 34523,
  ),
  test(
    nodes[0].children[1].children[0],
    88888,
  ),
  test(
    nodes[0].children[1],
    321123 + 88888 + 99999 + 34523,
  ),
  test(
    nodes[0].children[0],
    789654,
  ),
  test(
    nodes[0],
    123456 + 789654 + 321123 + 88888 + 99999 + 34523,
  ),
];

for (const result of results) console.log(result);

Answer 3

Using reduce is fine, but you need:

• recursion, so that this reduce is also called on the children when needed.
• to always assign to the total. Checking that it already exists is not useful, as it will not. And if it does, it is risky to rely on it, as you don't know whether the tree had been modified after that property was added.

let tree = [{id: 1,name: 'root',filesSize: 123456,children: [{id: 2,name: 'child 1',filesSize: 789654,}, {id: 3,name: 'child 2',filesSize: 321123,children: [{id: 4,name: 'child 3 - 1',filesSize: 88888,}, {id: 5,name: 'child 3 - 2',filesSize: 99999,children: [{id: 99999,name: 'child m - n',filesSize: 1234}]}]}]}];

let totalSize = tree.reduce(function recur(sum, child) {
    return sum + (child.total = (child.children ?? []).reduce(recur, child.filesSize));
}, 0);

// The returned size can be interesting when the top level has
// multiple entries (which is not the case in your example): 
console.log(totalSize);
console.log(tree);

Answer 4

const data = [{
  id: 1,
  name: 'root',
  filesSize: 123456,
  children: [{
      id: 2,
      name: 'child 1',
      filesSize: 789654,
    },
    {
      id: 3,
      name: 'child 2',
      filesSize: 321123,
      children: [{
          id: 4,
          name: 'child 3 - 1',
          filesSize: 88888,
        },
        {
          id: 5,
          name: 'child 3 - 2',
          filesSize: 99999,
          children: [{
            id: 99999,
            name: 'child m - n',
            filesSize: 12345,
          }]
        }]
    }]
}];

function calculateTotals(d) {
  let total = d.filesSize;
  if (d.children)
    d.children.forEach(c => total += calculateTotals(c));
  return d.total = total;
}
data.forEach(d => calculateTotals(d));
console.log(data);