How to convert a flat array to a tree with a specific maximum depth?

Question

I have a data like this:

[
  {
    id: "1",
    parent: null
  },
  {
    id: "2",
    parent: null
  },
  {
    id: "3",
    parent: "1"
  },
  {
    id: "4",
    parent: "3"
  },
]

And I want to convert it to a tree with a specific maximum depth. There are a few ways to convert an array to a tree, for example this package but the problem is they go all the way trough and create a deeply nested tree:

[
  {
    data: { id: "1", parent: null },
    children: [
      {
        data: { id: "3", parent: "1" }
        children: [
          {
            id: "4", parent: "3"
          } 
        ] 
      }
    ]
  },
  {
    data: { id: "2", parent: null }
  }
]

I don't want the depth of the tree be more than a specific amount, let say 1:

[
  {
    data: { id: "1", parent: null },
    children: [
      {
        data: { id: "3", parent: "1" }  
      },
      {
        data: { id: "4", parent: "3" } 
      }
    ]
  },
  {
    data: { id: "2", parent: null }
  }
]

One way is to first create the deeply nested object and then flatten the parts that I don't want to be nested, but it might change the order of items + it's inefficient. I've had a couple of tries to create an algorithm myself but I'm not generally good at these type of stuff. I would appreciate some help. Idea, example, anything could be useful.

Answer 1

Here's a solution that uses a little recursive generator to get the desired ancestor of the node based on the specified depth:

const treeify = (nodes, depth) => {
  const index = Object.fromEntries(
    nodes.map(node => [node.id, { ...node }])
  );
  const ancestry = function*(id) {
    if (id) {
      yield id;
      yield* ancestry(index[id].parent);
    }
  }
  
  nodes.forEach(node => {
    const [ancestor] = [...ancestry(node.parent)].slice(-depth);
    
    if (ancestor) {
      index[ancestor].children = index[ancestor].children || [];
      index[ancestor].children.push(index[node.id]);
    }
  });
  
  return Object.values(index).filter(node => !node.parent);
}

const data = [
  { id: "1", parent: null }, { id: "2", parent: null},
  { id: "3", parent: "1" }, { id: "4", parent: "3" }
];

console.log(treeify(data, 1));

I got rid of the superfluous data property. It wasn't being used consistently in your question anyway.