Group by Object from Array Object to Tree Object Javascript

Question

I need help group object like here: Input array is:

[
    {
        Id: '1234',
        Name: 'Country - Viet Nam',
        AdminLevel: 2
    },
    {
        Id:'5678',
        Name: 'Province - Ho Chi Minh',
        AdminLevel: 4,
        ParentId: '1234'
    },
    {
        Id:'91011',
        Name: 'Province - Ha Noi',
        AdminLevel: 4,
        ParentId: '1234'
    },
    {
        Id:'111213',
        Name: 'Province - Da Nang',
        AdminLevel: 4,
        ParentId: '1234'
    },
    {
        Id:'111213',
        Name: 'District - Quan 1',
        AdminLevel: 6,
        ParentId: '5678'
    },
    {
        Id:'111213',
        Name: 'District - Quan 2',
        AdminLevel: 6,
        ParentId: '5678'
    },
    {
        Id:'111213',
        Name: 'District - Quan 3',
        AdminLevel: 6,
        ParentId: '5678'
    },
    {
        Id:'111213',
        Name: 'District - Tinh nao do Ha Noi 1',
        AdminLevel: 6,
        ParentId: '91011'
    },
    {
        Id:'111213',
        Name: 'District - Tinh nao do Ha Noi 2',
        AdminLevel: 6,
        ParentId: '91011'
    },
    {
        Id:'111213',
        Name: 'District - Tinh nao do Ha Noi 3',
        AdminLevel: 6,
        ParentId: '91011'
    }
    
]

And expect out-put is:

{
    Id: '1234',
    Name: 'Country - Viet Nam',
    AdminLevel: 2,
    Data: [
        {
            Id:'5678',
            Name: 'Province - Ho Chi Minh',
            AdminLevel: 4,
            ParentId: '1234',
            Data: [
                {
                    Id:'111213',
                    Name: 'District - Quan 1',
                    AdminLevel: 6,
                    ParentId: '5678'
                },
                {
                    Id:'111213',
                    Name: 'District - Quan 2',
                    AdminLevel: 6,
                    ParentId: '5678'
                },
                {
                    Id:'111213',
                    Name: 'District - Quan 3',
                    AdminLevel: 6,
                    ParentId: '5678'
                }
            ]
        },
        {
            Id:'91011',
            Name: 'Province - Ha Noi',
            AdminLevel: 4,
            ParentId: '1234',
            Data: [
                {
                    Id:'111213',
                    Name: 'District - Tinh nao do Ha Noi 1',
                    AdminLevel: 6,
                    ParentId: '91011'
                },
                {
                    Id:'111213',
                    Name: 'District - Tinh nao do Ha Noi 2',
                    AdminLevel: 6,
                    ParentId: '91011'
                },
                {
                    Id:'111213',
                    Name: 'District - Tinh nao do Ha Noi 3',
                    AdminLevel: 6,
                    ParentId: '91011'
                }
            ]
        },
        {
            Id:'111213',
            Name: 'Province - Da Nang',
            AdminLevel: 4,
            ParentId: '1234'
        },
    ]
}

Explain: We have to group by AdminLevel and then group by ParentId.

• Look away we have structure : Country(Parent) - Province(Multiple - Child of Country) - District (Multiple - Child of Province). Thanks you so much for helping me

Answer 1

Assuming your data is ordered so that parents come before children, it's fairly straight forward:

1. Go through all the nodes
2. For each find the parent
3. Add to the parent's Data property (or create it first if it's not there yet)
4. Return the root node

The root node would be the one that doesn't have any parents. You can use a map to keep track of the visited items and make it easier to lookup the parents.

Since your data doesn't have unique IDs, you need to keep an array of items for each ID. If your data happens to have a parent ID that matches two or more things, then each of them will have the child node.

const data = [ { Id: '1234', Name: 'Country - Viet Nam', AdminLevel: 2 }, { Id:'5678', Name: 'Province - Ho Chi Minh', AdminLevel: 4, ParentId: '1234' }, { Id:'91011', Name: 'Province - Ha Noi', AdminLevel: 4, ParentId: '1234' }, { Id:'111213', Name: 'Province - Da Nang', AdminLevel: 4, ParentId: '1234' }, { Id:'111213', Name: 'District - Quan 1', AdminLevel: 6, ParentId: '5678' }, { Id:'111213', Name: 'District - Quan 2', AdminLevel: 6, ParentId: '5678' }, { Id:'111213', Name: 'District - Quan 3', AdminLevel: 6, ParentId: '5678' }, { Id:'111213', Name: 'District - Tinh nao do Ha Noi 1', AdminLevel: 6, ParentId: '91011' }, { Id:'111213', Name: 'District - Tinh nao do Ha Noi 2', AdminLevel: 6, ParentId: '91011' }, { Id:'111213', Name: 'District - Tinh nao do Ha Noi 3', AdminLevel: 6, ParentId: '91011' } ];

function group(arr) {
  let root;
  
  //keep a reference of all elements visited
  const lookup = new Map();
  
  //go through the array
  for (const item of arr) {
    //add to the lookup
    const key = item.Id;
    const value = lookup.get(key) ?? [];
    lookup.set(key, value.concat(item));
    
    if ("ParentId" in item){
      //find the parent(s) and update
      lookup.get(item.ParentId)
        .forEach(parent => {
          parent.Data = parent.Data ?? [];
          parent.Data.push(item);
        });
    } else {
      //if the item doesn't have a parent, it's the root node
      root = item;
    }
  }
  
  return root;
}

const result = group(data);

console.log(result);

If your data isn't ordered and parents might come before or after their children, the above code won't work, as it only visits and finds the parents in order, e.g., it will fail for [{Id: 2, ParentId: 1}, {Id: 1}]. If that happens to be the case, you can change the body of the function to first index all items, and then add them to their respective parents:

const data = [ { Id: '1234', Name: 'Country - Viet Nam', AdminLevel: 2 }, { Id:'5678', Name: 'Province - Ho Chi Minh', AdminLevel: 4, ParentId: '1234' }, { Id:'91011', Name: 'Province - Ha Noi', AdminLevel: 4, ParentId: '1234' }, { Id:'111213', Name: 'Province - Da Nang', AdminLevel: 4, ParentId: '1234' }, { Id:'111213', Name: 'District - Quan 1', AdminLevel: 6, ParentId: '5678' }, { Id:'111213', Name: 'District - Quan 2', AdminLevel: 6, ParentId: '5678' }, { Id:'111213', Name: 'District - Quan 3', AdminLevel: 6, ParentId: '5678' }, { Id:'111213', Name: 'District - Tinh nao do Ha Noi 1', AdminLevel: 6, ParentId: '91011' }, { Id:'111213', Name: 'District - Tinh nao do Ha Noi 2', AdminLevel: 6, ParentId: '91011' }, { Id:'111213', Name: 'District - Tinh nao do Ha Noi 3', AdminLevel: 6, ParentId: '91011' } ];

function group(arr) {
  let root;
  
  //keep a reference of all elements visited
  const lookup = new Map();
  
  //first index all items
  for (const item of arr) {
     //add to the lookup
    const key = item.Id;
    const value = lookup.get(key) ?? [];
    lookup.set(key, value.concat(item));
  }
  
  //go through the array
  for (const item of arr) {
    if ("ParentId" in item){
      //find the parent(s) and update
      lookup.get(item.ParentId)
        .forEach(parent => {
          parent.Data = parent.Data ?? [];
          parent.Data.push(item);
        });
    } else {
      //if the item doesn't have a parent, it's the root node
      root = item;
    }
  }
  
  return root;
}

const result = group(data);

console.log(result);

This is still an O(n) solution, since it's going to be growing linearly with the input.

Note that this isn't grouping by AdminLevel as there doesn't seem a need to. The data naturally groups based on the ParentId. Grouping by AdminLevel first is an extraneous operation given that you do not expect multiple groups to exist for each parent.

See a TypeScript solution using the same algorithm courtesy of jcalz