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)

Answer 2

If your input is already sorted by id and no child node can come before its parent Node in the list, then you can do this in one loop and don't even need recursion:

 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' }
];

const tasksById = Object.create(null);

// abusing filter to do the work of a forEach() 
// while also filtering the tasks down to a list with `parent: null`
const root = tasks.filter((value) => {
  const { id, parent } = value;
  
  tasksById[id] = value;
  
  if(parent == null) return true;
  
  (tasksById[parent].children || (tasksById[parent].children = [])).push(value);
});

console.log("rootNodes", root);
console.log("tasksById", tasksById);

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

Answer 3

I couldn't check for more test cases but this is something I was quickly able to come up with which passes your use case, it looks not so good, I would recommend to use it as initial structure and then build on it. Also, I am assuming that tasks are sorted in ascending order by parent, i.e child will only appear after its parent in tasks array

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' },
  { id: 6, parent: 5, value: 'Pour water over coffee grounds' },
  { id: 7, parent: 5, value: 'Pour water over coffee grounds' }
];

function Tree() {
  this.root = null;
  // this function makes node root, if root is empty, otherwise delegate it to recursive function
  this.add = function(node) {
    if(this.root == null)
      this.root = new Node(node);
    else
      // lets start our processing by considering root as parent
      this.addChild(node, this.root);
  }

  this.addChild = function(node, parent) {
    // if the provided parent is actual parent, add the node to its children
    if(parent.id == node.parent) {
      parent.children[node.id] = new Node(node);
    } else if(parent.children[node.parent]) {
      // if the provided parent children contains actual parent call addChild with that node
      this.addChild(node, parent.children[node.parent])
    } else if(Object.keys(parent.children).length > 0) {
      // iterate over children and call addChild with each child to search for parent
      for(let p in parent.children) {
        this.addChild(node, parent.children[p]);
      }
    } else {
      console.log('parent was not found');
    }
  }
}

function Node (node) {
  this.id = node.id;
  this.parent = node.parent;
  this.value = node.value;
  this.children = {};
}

const tree = new Tree();

// We are assuming that tasks are sorted in ascending order by parent

for(let t of tasks) {
  tree.add(t);
}

console.log(JSON.stringify(tree.root))

Let me know if you have questions. Lets crack it together