Create menu path from parent child relation

Issue

Given this array of objects:

[
  {
    "id": 1942,
    "label": "1",
    "url": "",
    "homepage": false,
    "visible": true,
    "order": 1
  },
  {
    "id": 1943,
    "label": "a",
    "url": "",
    "parentId": 1942,
    "homepage": false,
    "visible": true,
    "order": 1
  },
  {
    "id": 1944,
    "label": "aa",
    "url": "",
    "parentId": 1942,
    "homepage": false,
    "visible": true,
    "order": 2
  },
  {
    "id": 1945,
    "label": "aaa",
    "url": "",
    "parentId": 1942,
    "homepage": false,
    "visible": true,
    "order": 3
  },
  {
    "id": 1946,
    "label": "a1",
    "url": "",
    "parentId": 1943,
    "homepage": false,
    "visible": true,
    "order": 1
  },
  {
    "id": 1947,
    "label": "a2",
    "url": "",
    "parentId": 1943,
    "homepage": false,
    "visible": true,
    "order": 2
  },
  {
    "id": 1948,
    "label": "2",
    "url": "",
    "homepage": false,
    "visible": true,
    "order": 2
  },
  {
    "id": 1949,
    "label": "b",
    "url": "",
    "parentId": 1948,
    "homepage": false,
    "visible": true,
    "order": 1
  },
  {
    "id": 1950,
    "label": "b1",
    "url": "",
    "parentId": 1949,
    "homepage": false,
    "visible": true,
    "order": 1
  },
  {
    "id": 1951,
    "label": "bb",
    "url": "",
    "parentId": 1948,
    "homepage": false,
    "visible": true,
    "order": 2
  },
  {
    "id": 1952,
    "label": "b2",
    "url": "",
    "parentId": 1949,
    "homepage": false,
    "visible": true,
    "order": 2
  }
]

I need to create a menu with links based on parent child relations.

The new array i need has to have the following struture of objects.

1

1 / a

1 / aa

1 / aaa

1 / a / a1

1 / a / a2

2

2 / b

2 / bb

2 / b / b1

2 / b / b2

I have tried with recursion without luck:

 convert(array) {
    const x = array
      .filter((m, i) => m.id === array[i].parentId)
      .map((menuItem) => ({
        parent: menuItem,
        children: convert(array),
      }));
      console.log(x)
  }

And i tried with loops, but this aproach only gets limited levels and i need infinite levels of deep.

convert() {
    let parents = array.filter((p) => !p.parentId);
    const children = array.filter((c) => c.parentId);
    let combined = [];
    for (var i = 0; i < parents.length; i++) {
      for (var j = 0; j < children.length; j++) {
        if (children[j].parentId === parents[i].id) {
          combined.push([parents[i], children[j]]);
        }
      }
    }

    console.log(combined);
  }

EDIT: I was able to do it with 3 levels deep. But with recursion for "infinite" levels deep, could not figured out.

convert() {
    let parents = this.config.menuItems.filter((p) => !p.parentId);
    const children = this.config.menuItems.filter((c) => c.parentId);
    let combined = [];
    for (var i = 0; i < parents.length; i++) {
      for (var j = 0; j < children.length; j++) {
        if (children[j].parentId === parents[i].id) {
          combined.push([parents[i], children[j]]);
        }
        for (var k = 0; k < children.length; k++) {
          if (children[j].id === children[k].parentId && parents[i].id === children[j].parentId) {
            combined.push([parents[i], children[j], children[k]]);
          }
        }
      }
    }

    console.log(combined);
  }

Solution

Here's a recursive method that I think probably works. If you didn't want to use the page_children_map you could replace page_children_map.get(page.id) with pages.filter(({ parentId }) => parentId === page.id).

const pages = [{"id":1942,"label":"1","url":"","homepage":false,"visible":true,"order":1},{"id":1943,"label":"a","url":"","parentId":1942,"homepage":false,"visible":true,"order":1},{"id":1944,"label":"aa","url":"","parentId":1942,"homepage":false,"visible":true,"order":2},{"id":1945,"label":"aaa","url":"","parentId":1942,"homepage":false,"visible":true,"order":3},{"id":1946,"label":"a1","url":"","parentId":1943,"homepage":false,"visible":true,"order":1},{"id":1947,"label":"a2","url":"","parentId":1943,"homepage":false,"visible":true,"order":2},{"id":1948,"label":"2","url":"","homepage":false,"visible":true,"order":2},{"id":1949,"label":"b","url":"","parentId":1948,"homepage":false,"visible":true,"order":1},{"id":1950,"label":"b1","url":"","parentId":1949,"homepage":false,"visible":true,"order":1},{"id":1951,"label":"bb","url":"","parentId":1948,"homepage":false,"visible":true,"order":2},{"id":1952,"label":"b2","url":"","parentId":1949,"homepage":false,"visible":true,"order":2}];

const page_children_map = pages.reduce(
  (acc, val) => {
    if(!val.parentId) return acc;
    
    let arr = acc.get(val.parentId);
    if(!arr) acc.set(val.parentId, arr = []);

    arr.push(val);

    return acc;
  },
  new Map()
);

const page_paths = (page, parent_list = []) => {
  let paths = [];
  
  const list = [...parent_list, page];
  const children = page_children_map.get(page.id);
  
  paths.push(list);
  if(children?.length)
    paths.push(...children.flatMap((child) => page_paths(child, list)));
  
  return paths;
};

const res = pages
  .filter(({ parentId }) => !parentId)
  .reduce((acc, val) => {
    acc.push(...page_paths(val));
    return acc;
  }, [])
  .map( (crumbs) => crumbs.map(({ label }) => label).join(' / ') );

console.log(res);

Answered By - Ben Stephens