Performance issue when building a multi branch tree in Node.js

I think that the main bottleneck is algorithmic here. getChildren iterates over the entire people array, and it gets called for every single node. As the amount of elements in people increases, this cost adds up. It's been a long time since I last did algorithmic analysis, but I would throw an educated guess that the current implementation's time complexity is O(n^2).

I would solve this by using, for example, Map. I would go through the entire array once or twice to build a Map of node->children[], so that we can just do a fast O(1) lookup when recursing. This will help the time complexity but as a trade-off requires more memory because all of the elements are stored more than once in memory.

Here's an example:

function buildNodeChildLookup(people) {
  const nodeIdToNode = people.reduce((map, curr) => {
    map.set(curr.id, curr);
    return map;
  }, new Map());

  return people.reduce((map, curr) => {
    const children = map.get(curr.parentNode) || [];
    const childNode = nodeIdToNode.get(curr.id);
    children.push(childNode);
    map.set(curr.parentNode, children);
    return map;
  }, new Map());
}

// assume only one root!
const nodeIdToChildren = buildNodeChildLookup(people);

console.log(nodeIdToChildren)
// Map {
//   null => [ { id: '738a8f8a', parentNode: null } ],
//   '738a8f8a' => [
//     { id: 'd18fd69c', parentNode: '738a8f8a' },
//     { id: 'b507c11d', parentNode: '738a8f8a' }
//   ],
//   'b507c11d' => [
//     { id: '171d4709', parentNode: 'b507c11d' },
//     { id: '471b1cee', parentNode: 'b507c11d' }
//   ]
// }

Now that we have a fast lookup of "node id" -> "child nodes", we can just recurse from the root (the single node whose parent is null):

function buildHierarchy(node, nodeToChildren) {
  const children = nodeToChildren.get(node.id) || [];
  return {
    ...node,
    childNodes: children.map((child) => buildHierarchy(child, nodeToChildren)),
  };
}

As you can see, the buildHierarchy function is now much lighter as it just does a quick lookup for the node's children.

Putting it all together:

const people = [
  {
    id: "738a8f8a",
    parentNode: null,
  },
  {
    id: "d18fd69c",
    parentNode: "738a8f8a",
  },
  {
    id: "b507c11d",
    parentNode: "738a8f8a",
  },
  {
    id: "171d4709",
    parentNode: "b507c11d",
  },
  {
    id: "471b1cee",
    parentNode: "b507c11d",
  },
];

function buildNodeChildLookup(people) {
  const nodeIdToNode = people.reduce((map, curr) => {
    map.set(curr.id, curr);
    return map;
  }, new Map());

  return people.reduce((map, curr) => {
    const children = map.get(curr.parentNode) || [];
    const childNode = nodeIdToNode.get(curr.id);
    children.push(childNode);
    map.set(curr.parentNode, children);
    return map;
  }, new Map());
}

function buildHierarchy(node, nodeToChildren) {
  const children = nodeToChildren.get(node.id) || [];
  return {
    ...node,
    childNodes: children.map((child) => buildHierarchy(child, nodeToChildren)),
  };
}

// assume only one root!
const nodeIdToChildren = buildNodeChildLookup(people);
const root = nodeIdToChildren.get(null)[0];
console.log(buildHierarchy(root, nodeIdToChildren));

If this doesn't help, I would recommend profiling your application with Chrome's developer tools. They have great tools for finding which functions take time, or which functions exhaust memory.

While writing this answer, I saw @cbr's, and thought it was the same logic. But not entirely, and there seems to be a sensible performance difference (in Chrome at least), so I'll still post this one

I was not able to test this with real data that takes a long time to process, but I think your bottleneck is the use of filter in the getChildren function. For every single person, you are going through the entire people Array.

I think the time could be reduced by pre-processing the data only once, before building the hierarchy. To do this, we could create a Map, where each key is the ID of a person, and the value is an Array of its children.

This could be implemented like this:

// For each person
const childMap = people.reduce((map, person) => {
  // If its parentNode is not already in the map
  if (!map.has(person.parentNode)) {
    // Add it
    map.set(person.parentNode, []);
  }
  // Then, push the current person into that parent ID's children Array
  map.get(person.parentNode).push(person);
  return map;
}, new Map());

Then, your getChildren function would look like this:

function getChildren(parent) {
  return childMap.get(parent.id) || [];
}

Here is the full example, running 100.000 times in a row:

const people = [
  {
    id: '738a8f8a',
    parentNode: null
  },
  {
    id: 'd18fd69c',
    parentNode: '738a8f8a'
  },
  {
    id: 'b507c11d',
    parentNode: '738a8f8a'
  },
  {
    id: '171d4709',
    parentNode: 'b507c11d'
  },
  {
    id: '471b1cee',
    parentNode: 'b507c11d'
  }
];

const childMap = people.reduce((map, person) => {
  if (!map.has(person.parentNode)) {
    map.set(person.parentNode, []);
  }
  map.get(person.parentNode).push(person);
  return map;
}, new Map());

function getBase(base) {
  for (const person of base) {
    if (person.parentNode === null) {
      return person;
    }
  }
  return null;
}

function getChildren(parent) {
  return childMap.get(parent.id) || [];
}

function buildHierarchy(base = null) {
  if (base === null) {
    base = getBase(people);
    if (base === null) {
      return null;
    }
  }
  const children = getChildren(base);
  base.childrenNodes = children.map(buildHierarchy);
  return base;
}

console.time('x');
for (let i = 0; i < 100000; i++) buildHierarchy();
console.timeEnd('x');

Your code, running 100.000 times in a row:

const people = [
  {
    id: '738a8f8a',
    parentNode: null
  },
  {
    id: 'd18fd69c',
    parentNode: '738a8f8a'
  },
  {
    id: 'b507c11d',
    parentNode: '738a8f8a'
  },
  {
    id: '171d4709',
    parentNode: 'b507c11d'
  },
  {
    id: '471b1cee',
    parentNode: 'b507c11d'
  }
];

function getBase(base) {
  for (const person of base) {
    if (person['parentNode'] === null) {
      return person;
    }
  }
  return null;
}

function getChildren(parent) {
  const values = people.filter((person) => {
    return person['parentNode'] === parent['id'];
  });
  return Object.values(values);
}

function buildHierarchy(base = null) {
  if (base === null) {
    base = getBase(people);
    if (base === null) {
      return null;
    }
  }
  const children = getChildren(base).map((child) => {
    return buildHierarchy(child);
  });
  base['childrenNodes'] = children;
  return base;
}

console.time('x');
for (let i = 0; i < 100000; i++) buildHierarchy();
console.timeEnd('x');

@cbr's code, running 100.000 times in a row:

const people = [
  {
    id: "738a8f8a",
    parentNode: null,
  },
  {
    id: "d18fd69c",
    parentNode: "738a8f8a",
  },
  {
    id: "b507c11d",
    parentNode: "738a8f8a",
  },
  {
    id: "171d4709",
    parentNode: "b507c11d",
  },
  {
    id: "471b1cee",
    parentNode: "b507c11d",
  },
];

function buildNodeChildLookup(people) {
  const nodeIdToNode = people.reduce((map, curr) => {
    map.set(curr.id, curr);
    return map;
  }, new Map());

  return people.reduce((map, curr) => {
    const children = map.get(curr.parentNode) || [];
    const childNode = nodeIdToNode.get(curr.id);
    children.push(childNode);
    map.set(curr.parentNode, children);
    return map;
  }, new Map());
}

function buildHierarchy(node, nodeToChildren) {
  const children = nodeToChildren.get(node.id) || [];
  return {
    ...node,
    childNodes: children.map((child) => buildHierarchy(child, nodeToChildren)),
  };
}

// assume only one root!
const nodeIdToChildren = buildNodeChildLookup(people);
const root = nodeIdToChildren.get(null)[0];

console.time('x');
for (let i = 0; i < 100000; i++) buildHierarchy(root, nodeIdToChildren);
console.timeEnd('x');