[JS] Map flatten array to tree

mapFlattenToTree.js

import _ from 'lodash';

const originKey = '__origin';

const traverseTree = (root, test) => {
  let stack = [root];

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

    if (_.isArray(node)) {
      stack = [...stack, ...node];
    } else if (_.isObject(node)) {
      if (!test(node)) {
        const subtree = _.values(node);
        stack = [...stack, ...subtree];
      } else {
        return node;
      }
    }
  }

  return null;
};

const mapFlattenToTree = (flatten, mapElementToNode, isParent, childrenKey) => {
  const decoupledRoots = _.reduce(
    flatten,
    (tree, element) => {
      const parent = traverseTree(tree, node => isParent(node, element));
      const isOrphan = _.isNil(parent);
      const node = mapElementToNode(element);

      if (!isOrphan) {
        parent[childrenKey] = [...parent[childrenKey], node];
      }

      return isOrphan ? [...tree, { ...node, __origin: element }] : tree;
    },
    []
  );

  return _.reduce(
    decoupledRoots,
    (tree, root) => {
      const element = root[originKey];
      const cleanRoot = _.omit(root, originKey);
      const parent = traverseTree(tree, node => isParent(node, element));
      const isOrphan = _.isNil(parent);

      if (!isOrphan) {
        parent[childrenKey] = [...parent[childrenKey], cleanRoot];
      }

      const reducedTree = _.filter(tree, node => node !== root);
      return isOrphan ? [...reducedTree, cleanRoot] : reducedTree;
    },
    decoupledRoots
  );
};

const flatten = [{
  label: 'The 7',
  value: '7',
  parent_value: '6'
}, {
  label: 'The 1',
  value: '1',
  parent_value: '0'
}, {
  label: 'The 2',
  value: '2',
  parent_value: '0'
}, {
  label: 'The 3',
  value: '3',
  parent_value: '0'
}, {
  label: 'The 4',
  value: '4',
  parent_value: '1'
}, {
  label: 'The 5',
  value: '5',
  parent_value: '2'
}, {
  label: 'The 6',
  value: '6',
  parent_value: '2'
}];

const tree = mapFlattenToTree(
  // Flatten collection used to build a tree
  flatten,
  // Convert flatten collection element into tree node, including empty children list
  element => ({
    label: element.label,
    value: element.value,
    children: []
  }),
  // Test for parent-child relation
  (parent, child) =>
    parent.value === child.parent_value,
  // Name of children property (the one used in node mapping above)
  'children'
);

console.log(tree);

// [{
//     "label": "The 1",
//     "value": "1",
//     "children": [{
//         "label": "The 4",
//         "value": "4",
//         "children": []
//     }]
// }, {
//     "label": "The 2",
//     "value": "2",
//     "children": [{
//         "label": "The 5",
//         "value": "5",
//         "children": []
//     }, {
//         "label": "The 6",
//         "value": "6",
//         "children": [{
//             "label": "The 7",
//             "value": "7",
//             "children": []
//         }]
//     }]
// }, {
//     "label": "The 3",
//     "value": "3",
//     "children": []
// }]