Unflatten array of objects by key

Question

I have the following data structure:

[
  { id: 1, comment: "a", comment_id: null },
  { id: 2, comment: "b", comment_id: null }
  { id: 3, comment: "c", comment_id: null },
  { id: 4, comment: "d", comment_id: 1 },
  { id: 5, comment: "e", comment_id: 2 },
  { id: 6, comment: "f", comment_id: 3 },
  { id: 7, comment: "g", comment_id: 4 },
  { id: 8, comment: "h", comment_id: 7 },
  { id: 9, comment: "i", comment_id: 7 },
  { id: 10, comment: "i", comment_id: 9 },
]

I am trying to unflatten this array to put the comments within a children's array into their respective object so the data turns out like so:

[
  {
    "id":1,
    "comment":"a",
    "comment_id":null,
    "children":[
      {
        "id":4,
        "comment":"d",
        "comment_id":1,
        "children":[
          {
            "id":7,
            "comment":"g",
            "comment_id":4,
            "children":[
              {
                "id":8,
                "comment":"h",
                "comment_id":7
              },
              {
                "id":9,
                "comment":"i",
                "comment_id":7,
                "children":[
                  {
                    "id":10,
                    "comment":"i",
                    "comment_id":9
                  }
                ]
              }
            ]
          }
        ]
      }
    ]
  },
  {
    "id":2,
    "comment":"b",
    "comment_id":null,
    "children":[
      {
        "id":5,
        "comment":"e",
        "comment_id":2
      }
    ]
  },
  {
    "id":3,
    "comment":"c",
    "comment_id":null,
    "children":[
      {
        "id":6,
        "comment":"f",
        "comment_id":3
      }
    ]
  }
]

I know how to figure out what goes where with the following code, but I can't quite figure out a clean way to put it all into place.

const commentGrouping = allComments.reduce((groups:any, item:any) => {
  const group = (groups[item.comment_id || "root"] || []);
  group.push(item);
  groups[item.comment_id || "root"] = group;
  return groups;
}, {});

epascarello · Accepted Answer · 2022-12-16 19:54:48Z

2

You can do this with a simple look up reduce. No fancy recursion needed. Just one loop over the data.

const data = [
  { id: 1, comment: "a", comment_id: null },
  { id: 2, comment: "b", comment_id: null },
  { id: 3, comment: "c", comment_id: null },
  { id: 4, comment: "d", comment_id: 1 },
  { id: 5, comment: "e", comment_id: 2 },
  { id: 6, comment: "f", comment_id: 3 },
  { id: 7, comment: "g", comment_id: 4 },
  { id: 8, comment: "h", comment_id: 7 },
  { id: 9, comment: "i", comment_id: 7 },
  { id: 10, comment: "i", comment_id: 9 },
];


const tree = data.reduce((acc, item) => {
  // Find the parent and add it as a children
  acc[item.comment_id].children.push(item);

  // add a children array to our item
  item.children = [];

  // add the child to the look up so we can find it easily
  acc[item.id] = item;

  return acc;
}, { null: { children: [] } }).null.children;

console.log(tree);

If the data is not organized that parents are before the children

const data = [
  { id: 1, comment: "a", comment_id: null },
  { id: 2, comment: "b", comment_id: null },
  { id: 3, comment: "c", comment_id: null },
  { id: 4, comment: "d", comment_id: 1 },
  { id: 5, comment: "e", comment_id: 2 },
  { id: 6, comment: "f", comment_id: 3 },
  { id: 7, comment: "g", comment_id: 4 },
  { id: 8, comment: "h", comment_id: 7 },
  { id: 9, comment: "i", comment_id: 7 },
  { id: 10, comment: "i", comment_id: 9 },
];

const dataOpposite = data.reverse();


const tree = dataOpposite.reduce((acc, item) => {

  // does the parent exist? If no, create a placeholder
  if (!acc[item.comment_id]) {
    acc[item.comment_id] = { children: [] };
  }

  // Find the parent and add it as a children
  acc[item.comment_id].children.push(item);

  // add a children array to our item
  // if we have a placeholder created, use that
  item.children = acc[item.id]?.children || [];

  // add the child to the look up so we can find it easily
  acc[item.id] = item

  return acc;
}, { null: { children: [] } }).null.children;

console.log(tree);

edited Dec 16, 2022 at 19:54

answered Dec 16, 2022 at 19:39

epascarello

208k20 gold badges206 silver badges246 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Wyck Over a year ago

This relies on the list being ordered such that you will never encounter a child before its parent.

epascarello Over a year ago

Well if that is the case it is simple to either sort or to add a placeholder. If that edge cases exists it is literally a few lines of code extra.

Wyck Over a year ago

A sort would furthermore require that the id of every parent is a smaller number than the id of any of its children.

epascarello Over a year ago

@Wyck I edited it to make you happy....

Wyck Over a year ago

I wasn't unhappy. I quite liked your original answer -- it just comes with a couple of prerequisites so I thought I'd mention them in a comment.

|

Keith · Accepted Answer · 2022-12-16 19:21:13Z

0

Rather than reduce, you might want to use recursion, tree structures work well with recursion.

eg.

const data = [
  { id: 1, comment: "a", comment_id: null },
  { id: 2, comment: "b", comment_id: null },
  { id: 3, comment: "c", comment_id: null },
  { id: 4, comment: "d", comment_id: 1 },
  { id: 5, comment: "e", comment_id: 2 },
  { id: 6, comment: "f", comment_id: 3 },
  { id: 7, comment: "g", comment_id: 4 },
  { id: 8, comment: "h", comment_id: 7 },
  { id: 9, comment: "i", comment_id: 7 },
  { id: 10, comment: "i", comment_id: 9 }
];

function fillTree(parentId) {
   const ret = data.filter(d => d.comment_id === parentId);
   for (const s of ret) {
     const sh = fillTree(s.id);
     if (sh.length) s.children = sh;
   }
   return ret;
}

console.log(fillTree(null));

answered Dec 16, 2022 at 19:21

Keith

24.4k2 gold badges32 silver badges48 bronze badges

2 Comments

epascarello Over a year ago

I works, just not very efficient since you loop over the data many times.

Keith Over a year ago

@epascarello Yeah, if performance was an issue, I'd map it first on comment_id, giving a O(2n) complexity. Another advantage of course with using recursion is it's way easier for others to understand, and refactor. eg. Lets say the source data is not an array, but it's async data coming from a database, the recursion code could still be used with minimal changes, but the Array.reduce is now defunct..

Collectives™ on Stack Overflow

Unflatten array of objects by key

2 Answers 2

8 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related