How can i recursively group children objects under parent in an array of objects in JavaScript?

I have an array of topics each linked to a parent topic. So, basically what I want to do is form an array with all the children topics nested under the parent. So if I had an table of topics looking like this:

id	name	parent_id
1	Topic 1	null
2	Topic 2	1
3	Topic 3	2
4	Topic 4	2
5	Topic 5	4

And if the json array looks like this:

[
  { id: 1, name: "Topic 1", parent_id: null },
  { id: 2, name: "Topic 2", parent_id: 1 },
  { id: 3, name: "Topic 3", parent_id: 2 },
  { id: 4, name: "Topic 4", parent_id: 2 },
  { id: 5, name: "Topic 5", parent_id: 4 },
]

I want the output array to look like this:

[
  {
    id: 1,
    name: "Topic 1",
    children: [
      {
        id: 2,
        name: "Topic 2",
        children: [
          { id: 3, name: "Topic 3", children: [] },
          {
            id: 4,
            name: "Topic 4",
            children: [{ id: 5, name: "Topic 5", children: [] }],
          },
        ],
      },
    ],
  },
]

Answer

assume nothing, control everything

A tree is a graph with parent->child relationships between the nodes. To construct this graph efficiently, we must first index the flat array of nodes –

{
  A => [child, child, child, ...],
  B => [child, child, ...],
  C => [...],
  ...
}

The input array does not need to be ordered in a specific way for this technique to work. In fact, it’s important that our modules make no assumptions about the order or shape of our data. This puts the caller (you!) in control and ensures the highest degree of flexibility and reusability –

import * as index from "./index.js"
import * as graph from "./graph.js"

const data = [
  { id: 1, name: "Topic 1", parent_id: null },
  { id: 2, name: "Topic 2", parent_id: 1 },
  { id: 3, name: "Topic 3", parent_id: 2 },
  { id: 4, name: "Topic 4", parent_id: 2 },
  { id: 5, name: "Topic 5", parent_id: 4 },
]

const tree = 
  graph.new(
    // create index by foreign key, node.parent_id
    index.new(data, node => node.parent_id),
    // construct node's children using primary key, node.id
    (node, children) => ({...node, children: children(node.id)})
  )

console.log(JSON.stringify(tree, null, 2))

[
  {
    "id": 1,
    "name": "Topic 1",
    "parent_id": null,
    "children": [
      {
        "id": 2,
        "name": "Topic 2",
        "parent_id": 1,
        "children": [
          {
            "id": 3,
            "name": "Topic 3",
            "parent_id": 2,
            "children": []
          },
          {
            "id": 4,
            "name": "Topic 4",
            "parent_id": 2,
            "children": [
              {
                "id": 5,
                "name": "Topic 5",
                "parent_id": 4,
                "children": []
              }
            ]
          }
        ]
      }
    ]
  }
]

Did you notice how index.new accepts a function to declare the node’s foreign key and graph.new uses the node’s primary key? This means you can reuse these modules for nodes of any shape or arrangement, without needing to modify the module’s code. Let’s review index and graph now –

// index.js

const empty = _ =>
  new Map

const update = (t, k, f) =>
  t.set(k, f(r.get(k)))

const append = (t, k, v) =>
  update(t, k, (a = []) => [...a, v])

const _new = (a = [], f) =>
  a.reduce((t, v) => append(t, f(v), v), empty())

export { empty, update, append, new:_new }

// graph.js

const empty = _ =>
  {}

const _new = (i, f, root = null) => {
  const many = (a = []) =>
    a.map(v => one(v))
  const one = (v) =>
    f(v, next => many(i.get(next)))
  return many(i.get(root))
}

exports { empty, new:_new }

Expand and run the code below to verify the result in your own browser –

const callcc = f => {
  const box = Symbol()
  try { return f(unbox => { throw {box, unbox} }) }
  catch (e) { if (e?.box == box) return e.unbox; throw e  }
}

// stacksnippets doesn't support modules yet
const module = callcc

const index = module(exports => {
  const empty = _ => new Map
  const update = (t, k, f) =>
    t.set(k, f(t.get(k)))
  const append = (t, k, v) =>
    update(t, k, (a = []) => [...a, v])
  const _new = (a = [], f) =>
    a.reduce((t, v) => append(t, f(v), v), empty())
  exports({ empty, update, append, new:_new })
})

const graph = module(exports => {
  const empty = _ => {}
  const _new = (i, f, root = null) => {
    const many = (a = []) =>
      a.map(v => one(v))
    const one = (v) =>
      f(v, next => many(i.get(next)))
    return many(i.get(root))
  }
  exports({ empty, new:_new })
})

const data = [
  { id: 1, name: "Topic 1", parent_id: null },
  { id: 2, name: "Topic 2", parent_id: 1 },
  { id: 3, name: "Topic 3", parent_id: 2 },
  { id: 4, name: "Topic 4", parent_id: 2 },
  { id: 5, name: "Topic 5", parent_id: 4 },
]

const tree = 
  graph.new(
    // create index by node.parent_id
    index.new(data, node => node.parent_id),
    // construct node's children using node.id
    (node, children) => ({...node, children: children(node.id)})
  )

console.log(JSON.stringify(tree, null, 2))

.as-console-wrapper { min-height: 100%; top: 0 }