Grouping elements with parentId, child relationship into groups

I’d like to generate this logic of grouping.

The image is what I’m trying to draw out of the result, it describes the relationship between the children, parent, and grouping

Using this data set

const nodes = [{
        "id": "9",
        "root":true,
        "parentIds": []
    },
    {
        "id": "3",
        "parentIds": [
            "9"
        ]
    },
    {
        "id": "2",
        "parentIds": [
            "3"
        ]
    },
    {
        "id": "4",
        "parentIds": [
            "9"
        ]
    },
    {
        "id": "1",
        "parentIds": [
            "4",
            "5",
            "6"
        ]
    },
    {
        "id": "8",
        "parentIds": [
            "9"
        ]
    },
    {
        "id": "5",
        "parentIds": [
            "8"
        ]
    },
    {
        "id": "7",
        "parentIds": [
            "9"
        ]
    },
    {
        "id": "6",
        "parentIds": [
            "7"
        ]
    }
]

Each node has a parentIds property indicating where it belongs to and grouping them, if there is a 1-1 relationship it adds a new group under the previous one and so on, eventually creating a tree of groups (and nodes if remaining).

My main question is how can apply that logic to what I currently have with the dataset flat array?

After grouping it would return a tree like array structure such as this (color property is irrelevant, its just there for visual aid)

  const tree = [
    {
      groupNumber: 1,
      color: "purple",
      children: [
        {
          groupNumber: 2,
          color: "blue",
          children: [
            {
              groupNumber: 4,
              color: "green",
              children: [{ nodeId: "6" }, { nodeId: "7" }],
            },
            {
              groupNumber: 5,
              color: "yellow",
              children: [{ nodeId: "5" }, { nodeId: "8" }],
            },
            { nodeId: "1" },
            { nodeId: "4" },
          ],
        },
        {
          groupNumber: 3,
          color: "red",
          children: [{ nodeId: "2" }, { nodeId: "3" }],
        },
        { nodeId: "9" },
      ],
    },
  ];