Build a tree array (3 dimensional) from a flat array in Typescript/Javascript

I have incoming data in this format:

const worldMap = [
  {
    "name": "Germany",
    "parentId": null,
    "type": "Country",
    "value": "country:unique:key:1234",
    "id": "1",
  },
  {
    "name": "North Rhine",
    "parentId": "1",
    "type": "State",
    "value": "state:unique:key:1234",
    "id": "2",
  },
  {
    "name": "Berlin",
    "parentId": "1",
    "type": "State",
    "value": "state:unique:key:1234",
    "id": "3",
  },  
  {
    "name": "Dusseldorf",
    "parentId": "2",
    "type": "city",
    "value": "city:unique:key:1234",
    "id": "4",
  },
   {
    "name": "India",
    "parentId": null,
    "type": "Country",
    "value": "country:unique:key:1234",
    "id": "5",
  }, 
];

I want the output to be something like this:

[
   {
   label: "Germany",
   value: "country:unique:key:1234",
   subs: [
    {
        label: "North Rhine",
        value: "state:unique:key:1234",
        subs: [
            {
                label: "Dusseldorf",
                value: "city:unique:key:1234",
            }
        ]
    },
    {
       label: "Berlin",
       value: "state:unique:key:1234",
    }
   ]
   }
   ,
   {
       "label": "India",
       "value": "country:unique:key:1234"
   }
]

Basically, it is a three dimensional array with first level being the Countrie, second States and third Cities. I have tried the following code:

let tempCountries = [];

worldMap.map((world) => {
  if (world.parentId == null && world.type == "Country") {
    tempCountries.push({label: world.name, value: world.value, id: world.id});
  }
});


tempCountries.map((tempCountry) => {
  const states = worldMap.find((x) => x.parentId == tempCountry.id);
  console.log("=== states ===", states);
  if (states !== undefined) {
      tempCountries.find((x)=>x.id == tempCountry.id).children.push(states)
  }
});

But the above code works upto second level and does not add cities to states. Could anyone please help me achieve this ?

Thanks a lot!

Answer

You can use a recursive solution:

function convertToTree(layer, parentId = null) {
    const vertex = new Map(), others = [];

    layer.forEach(item => {
        if (item.parentId === parentId) {
            vertex.set(item.id, { label: item.name, value: item.value });
        } else {
            others.push(item);
        }
    });

    for (const vertexId of vertex.keys()) {
        const subs = convertToTree(others, vertexId);
        if (subs.length) {
            vertex.get(vertexId).subs = subs;
        }
    }

    return [...vertex.values()];
}