Create a nested array of objects from flat object array with childIds

Question

I have a flat array of objects that I need in a (deeply) nested array of objects.

My flat array (IDs are random in reality, but changed here for clarity, and nesting can be very deep):

const tags = [
  {
    id: 'tag1',
    title: 'Tag 1',
    childIds: ['tag11', 'tag12'],
    root: true
  },
  {
    id: 'tag11',
    title: 'Tag 11',
    childIds: ['tag111', 'tag112'],
  },
  {
    id: 'tag12',
    title: 'Tag 12',
    childIds: ['tag121']
  },
  {
    id: 'tag111',
    title: 'Tag 111',
    childIds: []
  },
  {
    id: 'tag112',
    title: 'Tag 112',
    childIds: []
  },
  {
    id: 'tag121',
    title: 'Tag 121',
    childIds: []
  }
]

My desired output:

tagsNested = [
  {
    id: 'tag1',
    title: 'Tag 1',
    tags: [
      {
        id: 'tag11',
        title: 'tag 11',
        tags: [
          {
            id: 'tag111',
            title: 'Tag 111',
            tags: []
          },
          {
            id: 'tag112',
            title: 'Tag 112',
            tags: []
          }
        ]
      },
      {
        id: 'tag12',
        title: 'tag 12',
        tags: [
          {
            id: 'tag121',
            title: 'Tag 121',
            tags: []
          }
        ]
      }
    ]
  }

]

My best effort so far keeps nesting all tags under any tag.

I.e. I do get a nested array, but each tags-array contains all tags.

function unflatten(tag, nestedTags) {
  if (tag.childIds) {
    tag.childIds.forEach((childId) => {
      var childTag = tags.find((t) => t.id === childId)
      childTag.tags = unflatten(childTag, nestedTags)
      nestedTags.push(childTag)
    })
  }
  return nestedTags
}
const rootTag = tags.find((tag) => tag.root)
console.log(unflatten(rootTag, []))

I really struggle with these recursive functions and figuring out how to make the return statements give me the right data.

gedhean · Accepted Answer · 2020-04-18 20:38:28Z

This is a recursive approach. It works like that:

Given the root tag (or any tag) and tagsArray (flatten array of tags)
Filter all children tags of root
Then for each child find all its children tags
Then return the tag when there is no more children tags

You might try this code snippet:

const tags = [
  {
    id: 'tag1',
    title: 'Tag 1',
    childIds: ['tag11', 'tag12'],
    root: true
  },
  {
    id: 'tag11',
    title: 'Tag 11',
    childIds: ['tag111', 'tag112'],
  },
  {
    id: 'tag12',
    title: 'Tag 12',
    childIds: ['tag121']
  },
  {
    id: 'tag111',
    title: 'Tag 111',
    childIds: []
  },
  {
    id: 'tag112',
    title: 'Tag 112',
    childIds: []
  },
  {
    id: 'tag121',
    title: 'Tag 121',
    childIds: []
  }
]

function buildTag({id, title, childIds}, tagsArray) {
  const tags = tagsArray
    .filter(tag => childIds.includes(tag.id))
    .map(tag => buildTag(tag, tagsArray))

  return {
      id,
      title,
      tags,
    }
}

const rootTag = tags.find((tag) => tag.root)
console.log([buildTag(rootTag, tags)])

/* 
tagsNested = [
  {
    id: 'tag1',
    title: 'Tag 1',
    tags: [
      {
        id: 'tag11',
        title: 'tag 11',
        tags: [
          {
            id: 'tag111',
            title: 'Tag 111',
            tags: []
          },
          {
            id: 'tag112',
            title: 'Tag 112',
            tags: []
          }
        ]
      },
      {
        id: 'tag12',
        title: 'tag 12',
        tags: [
          {
            id: 'tag121',
            title: 'Tag 121',
            tags: []
          }
        ]
      }
    ]
  }
]
*/

This works, but is not efficient. It has a O(n²) time complexity, while it can be done with O(n) time complexity.

trincot · Accepted Answer · 2020-04-18 20:23:43Z

You can use a Map to key each node, and then make the new object format from that. Finally delete the entries from the map that have parents, so that the root remains. So really, the root property is not needed. It follows indirectly from the given relationships. This algorithm does not use that property:

const tags = [{id: 'tag1',title: 'Tag 1',childIds: ['tag11', 'tag12'],root: true},{id: 'tag11',title: 'Tag 11',childIds: ['tag111', 'tag112'],},{id: 'tag12',title: 'Tag 12',childIds: ['tag121']},{id: 'tag111',title: 'Tag 111',childIds: []},{id: 'tag112',title: 'Tag 112',childIds: []},{id: 'tag121',title: 'Tag 121',childIds: []}];

let map = new Map(tags.map(({id, title, childIds}) => [id, { id, title, tags: [] }]));
tags.forEach(tag => map.get(tag.id).tags = tag.childIds.map(id => map.get(id)));
tags.forEach(tag => tag.childIds.forEach(id => map.delete(id)));
let tagsNested = [...map.values()];
console.log(tagsNested);

Nina Scholz · Accepted Answer · 2020-04-18 20:32:59Z

You could take an iterative approach with an object as reference to the nodes.

const tags = [{ id: 'tag1', title: 'Tag 1', childIds: ['tag11', 'tag12'], root: true }, { id: 'tag11', title: 'Tag 11', childIds: ['tag111', 'tag112'] }, { id: 'tag12', title: 'Tag 12', childIds: ['tag121'] }, { id: 'tag111', title: 'Tag 111', childIds: [] }, { id: 'tag112', title: 'Tag 112', childIds: [] }, { id: 'tag121', title: 'Tag 121', childIds: [] }],
    tree = function (array) {
        var t = {},
            tree = [];

        array.forEach(({ id, title, childIds, root }) => {
            Object.assign(
                t[id] = t[id] || {},
                { id, title, tags: childIds.map(id => t[id] = t[id] || { id }) }
            );
            if (root) tree.push(t[id]);
        });

        return tree;
    }(tags);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Oleksandr Fedotov · Accepted Answer · 2020-04-20 04:58:20Z

0

Here is a codesandbox - https://codesandbox.io/s/green-dawn-3gpvz?file=/src/index.js. The only difference with your requirement is result is just an object not an array, but you can simply wrap this single element to be an array

function resolveChildren(tag, allTags) {
  const { childIds, root, ...rest } = tag;
  if (!childIds) return rest;

  return {
    ...rest,
    tags: childIds.map(childId =>
      resolveChildren(allTags.find(t => t.id === childId), allTags)
    )
  };
}

resolveChildren(tags.find(tag => !!tag.root), tags)

edited Apr 20, 2020 at 4:58

answered Apr 18, 2020 at 20:27

Oleksandr Fedotov

3842 silver badges8 bronze badges

1 Comment

Scott Sauyet Over a year ago

Please include code in your answers. An external link is fine as well, especially if it can offer more context, but the relevant code should always be available here.

Collectives™ on Stack Overflow

Create a nested array of objects from flat object array with childIds

4 Answers 4

1 Comment

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related