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.

CodePudding user response：

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.

CodePudding user response：

You'll anyway have to iterate all of the data, so use that iteration to inverse the relationship and collect for each parent the list of children ids. This almost looks like the complete tree structure you want to avoid, but it uses less memory, as these arrays only consist of ids, not of objects. And, you really need to have a fast look up and avoid repeated iterations over the same input (like with find).

This intermediate structure is an adjacency list. In a second phase it can be used to build the limited tree object structure:

const createAdjacencyList = data =>
    data.reduce((graph, {id, parent}) =>
        ((graph[parent] ??= []).push(id), graph)
    , {});

const createTree = (adj, depth, parent=null) =>
    adj[parent].map(id => ({
        id, parent,
        ...depth && adj[id] && { 
            children: createTree(adj, depth-1, id) 
        }
    }));

// Example
const data = [{id: "1",parent: null},{id: "2",parent: null},{id: "3",parent: "1"},{id: "4",parent: "3"}];
const adj = createAdjacencyList(data);
const tree = createTree(adj, 1);
console.log(tree);

CodePudding user response：

This code builds the tree using a standard recursive approach, except when the specified depth is reached. At that depth, it builds a flat array instead of continuing to build out the tree.

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

const f = (depth, p=null) => d.filter(i => i.parent===p).map(i => depth>0 ?
  {data:i, children: f(depth-1, i.id)} : [{data:i}, ...f(0,i.id).flat()]);

console.log(f(1));

However, the code above will order the 'flat' parts of the tree according to the tree hierarchy. To ensure that the 'flat' parts contain items in the same order as the original data, include a sort:

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

const lookup = ({data:{id}}) => d.findIndex(d=>id===d.id);

const f = (depth, p=null) => d.filter(i => i.parent===p).map(i => depth>0 ?
  {data:i, children: f(depth-1, i.id)} : [{data:i}, ...f(0,i.id).flat()]
  .sort((a,b)=>lookup(a)-lookup(b)));

console.log(f(1));