Create a recursive function that takes a flat array and converts to a tree data structure

Question

So I'm trying to write a recursive function that takes a flat array of objects with their value, id, and the id of their parent node and transform it to a tree structure, where the children of the structure are an array of nodes. Children need to be sorted by id and if its null it can be the root node.

The function im trying to write function toTree(data), only should take in the data array. I've been unable to do it without a parent. What I have so far is a function(below) that takes data and parent to get started.

input:

 const tasks = [
  { id: 1, parent: null, value: 'Make breakfast' },
  { id: 2, parent: 1, value: 'Brew coffee' },
  { id: 3, parent: 2, value: 'Boil water' },
  { id: 4, parent: 2, value: 'Grind coffee beans' },
  { id: 5, parent: 2, value: 'Pour water over coffee grounds' }
];

output:

{
  id: 1,
  parent: null,
  value: 'Make Breakfast',
  children: [
     {
       id: 2,
       parent: 1,
       value: 'Brew coffee',
       children: [
          { id: 3, parent: 2, value: 'Boil water' },
          { id: 4, parent: 2, value: 'Grind coffee beans' },
          { id: 5, parent: 2, value: 'Pour water over coffee grounds'     }
       ]
     }
  ]
}


funciton toTree(data) {
  customtoTree (data, null);
}

function customToTree (data, parent) {
  const out = [];
  data.forEach((obj) => {
    if (obj.parent === parent) {
      const children = customToTree(data,obj.parent);

      if (children.length) {
        obj[children[0]] = children;
      }
      const {id,parent, ...content} = obj;
      out.push(content);
    }
  });
  return out;
}

I would really like to understand the correct logic on how to do this and think about this and how to do it without giving a parent explicitly.

Answer 1

I had the same question during an interview, and I haven't been able to solve it. I was also confused that the function should only take the array as a first and only argument.

But after reworking it later (and with some very good suggestions from a brilliant man), I realized that you can call the function with the array as the first and only argument the first time and then during the recursion call passing the parent as a second argument.

Inside the function, you only need to check if the second argument is undefined, if it is, you search in the array for your root object and assign it to your second argument.

So here is my solution, I hope it will be clearer :

function toTree(arr, item) {

        if (!item) {
            item = arr.find(item => item.parent === null)
        }

        let parent = {...item}
        parent.children = 
            arr.filter(x => x.parent === item.id)
                .sort((a, b) => a.id - b.id)
                .map(y => toTree(arr, y))

        return parent     
}

toTree(tasks)