How to denormalize normalized data most effectively in javascript

Question

For example I have the following tree:

root: {
  a: {
    b: null,
    c: {
      d: null
    }
  }
  e: null
}

I receive it in the shape of { [child]: parent }:

{
  a: 'root',
  e: 'root',
  b: 'a',
  c: 'a',
  d: 'c'
}

But I don't receive it ordered as above. However, I would like to.

If I know that the root item (that doesn't have a parent) is root, I can work with this function:

const recurs = (obj, cb, parent = 'root') => Object.entries(obj)
  .filter(([child, childsParent]) => childsParent === parent)
  .forEach(([child]) => {
    cb(child);
    recurs(obj, cb, child);
  });

But because it's recursive, it can fill the memory because the parents won't be garbage collected until everything finishes. Is there a more efficient way to do this kind of things? Can this be converted to a for loop?

Answer 1

Use a lookup table that is filled in a single linear loop:

const edges = {
  a: 'root',
  e: 'root',
  b: 'a',
  c: 'a',
  d: 'c'
};

const forest = {};
for (const child in edges) {
  const parent = edges[child];
  forest[parent] ??= {};
  forest[child] ??= {};
  forest[parent][child] = forest[child];
}
const tree = forest.root;