Implement javascript function using tail recursion

Question

I have got a flat array representing a tree, and I want to build a nested object using tail recursion.

I've got the following code to run and generate the desired output, but I am not sure if it is a proper implementation of tail recursion.

Please advice :)

const myArray = [
  { id: 'root' },
  { id: 0, parent: 'root' },
  { id: 1, parent: 'root' },
  { id: 2, parent: 0 },
  { id: 3, parent: 1 },
  { id: 4, parent: 2 },
  { id: 5, parent: 1 },
  { id: 6, parent: 4 },
  { id: 7, parent: 0 },
  { id: 8, parent: 0 },
];


function makeNestedTreeFromArray(array, id, children) {
  if (children.length <= 0) {
    return array.find(entry => entry.id === id);
  }
  return ({
    ...array.find(entry => entry.id === id),
    children: children.map(child => makeNestedTreeFromArray(
      array,
      child.id,
      array.filter(entry => entry.parent === child.id),
    ))
  });
}

const myTree = makeNestedTreeFromArray(
  myArray,
  'root',
  myArray.filter(entry => entry.parent === 'root'),
);

console.log(myTree);

Answer 1

The basics of a tail recursion is to return the same function with changed parameters. This allows to replace the last stack entry with the new call of the function without increasing the stack size.

The following approach uses a TCO and returns the function call and uses a standard exit condition to return from a recursive function at the top of the function.

The algorithm visits each item only ones and builds a tree which has multiple roots. At the end only the wanted root is returned. This approach works for unsorted data, because for every node, both information of id and parent are used and their relation is preserved.

function getTree(data, root, index = 0, tree = {}) {
    var o = data[index];
    if (!o) return tree[root];
    Object.assign(tree[o.id] = tree[o.id] || {}, o);
    tree[o.parent] = tree[o.parent] || {};
    tree[o.parent].children = tree[o.parent].children || [];
    tree[o.parent].children.push(tree[o.id]);
    return getTree(data, root, index + 1, tree);
}

const
    data = [{ id: 'root' }, { id: 0, parent: 'root' }, { id: 1, parent: 'root' }, { id: 2, parent: 0 }, { id: 3, parent: 1 }, { id: 4, parent: 2 }, { id: 5, parent: 1 }, { id: 6, parent: 4 }, { id: 7, parent: 0 }, { id: 8, parent: 0 }],
    tree = getTree(data, 'root');

console.log(tree);

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

Answer 2

Your function does not have a tail call and it won't under all circumstances, because you call the recursive call more than once: Remember that tail call optimization basically means that the function is turned into a loop, ... which is impossible for this case.

That said, instead of finding all the nested elements recursively and iterating over the array a lot of times, use a id to object Map, then you just need to iterate twice: Once to build up the Map, and a second time to link each element to it's parent. A great implementation of that can be found here.

Here would be a tail-call version (I would just use a loop here though):

 function listToTree([el, ...rest], parent = new Map, roots = []) {
   if(el.parentID)
      parent.get(el.parentID).children.push(el);
   else roots.push(el);

   parent.set(el.id, el);
   el.children = [];

   if(!rest.length) return roots;

   return listToTree(rest, parent, roots); // A proper tail call: This can be turned into a loop
 }