How to understand a fragment of code of function that converts array to treeArray in javascript react?

Question

I have function that converts simple array of objects to treeArray. The function was not written by me. The function uses lodash _.each. It is the same as native forEach

Here the code and sample data:

let a = [
    {
        id: 1,
        name: "ADMINISTRATION"
    },
    {
        id: 2,
        name: "ADMIN_GROUP",
        parentId: 1
    },
    {
        id: 3,
        name: "ADMIN_GROUP_CREATE",
        parentId: 2
    },
    {
        id:168,
        name: "HELP_EDIT"
    }
]


function makeTreeFromArray(list) {
  const treeArray = [];
  const treeMap = {};

  _.each(list, (item, index) => {
    treeMap[item.id] = index;
    // list[index].children = [];
    item.children = [];
  });

  _.each(list, item => {
    if (item.parentId) {
      list[treeMap[item.parentId]].children.push(item);
    } else {
      treeArray.push(item);
    }
  });

  console.log('treeMap', treeMap);
  console.log('list', list);
  return treeArray;
}

const newArr = makeTreeFromArray(a);
console.log(newArr);

And here is the output:

I didn't understand this fragment of code:

...
_.each(list, item => {
    if (item.parentId) {
      list[treeMap[item.parentId]].children.push(item);
    } else {
      treeArray.push(item);
    }
...

I obtain a treeArray of two objects but why there are two objects? I am really tired and confused. Here, initially treeArray is empty. Then, item is pushed only if it doesn't have "parentId". If it has "parentId" - appropriate logic is applied. and each child is pushed to corresponding parent's "children" property. And original list mutated. But there is no 'smell' of treeArray. Complex parent object is in list array. Am I right? But why at the end, treeArray consists of two objects not one ? Why Complex parent object magically appears in treeArray?

Answer 1

I obtain a treeArray of two objects but why there are two objects?

You rightly identify that objects that do not have a parentId are appended in that array. There are two such objects in your input array. As they don't have a reference to a parent, they should be treated as top-level objects, and that is why you should see exactly two objects in your treeArray. All other input objects should be found somewhere deeper in some children property.

If it has "parentId" - appropriate logic is applied. and each child is pushed to corresponding parent's "children" property. And original list mutated. But there is no 'smell' of treeArray.

Indeed, treeArray is not referenced in that part of the code. But sooner or later we will have an object A, whose parent object (B) will be a top-level object, i.e. which does not have a parent.

We know that when B is visited (maybe before A or after A, that doesn't matter), it will be added to treeArray. So although treeArray is not directly referenced, by adding A to the children property of B, we influence what is (or will be) pushed in treeArray.

In other words: by mutating B's children property (as we add A to it), we also (indirectly) mutate treeArray (if B was already in it), or will push a mutated B into treeArray (if B was still to be added to it).

So by adding objects into the children array of other objects, we create a conglomerate of nested objects. Only the objects that do not have a parent, remain "independent": they end up in treeArray, but "drag" with them a subtree with all the nested children objects, and those may have their own children objects, ...etc.

Answer 2

It's quite a simple way to generate a tree, but you ideally need to understand pointers/references in JavaScript to understand how it works. (It does create a lot of pointers/references, there would be other ways to do it with less pointers and possibly less memory usage too. Also, this will only work if the flat list is ordered and it does mutate the original list. There are other ways to generate trees from flat arrays, using recursion etc. and without mutating the list)

Important is that primitives (numbers, booleans, etc.) are stored on the stack and objects (like Arrays, Objects, etc.) are stored on the heap. Variables for objects are just pointers to the object location on the heap. I am not sure what article or YouTube video to recommend as I read/watched so many different ones - https://www.google.com/search?q=stack+vs+heap

Sticking to your example, let me try to explain line by line (with comments in the code):

let a = [
    {   id: 1,    name: "ADMINISTRATION"    },
    {   id: 2,    name: "ADMIN_GROUP",        parentId: 1    },
    {   id: 3,    name: "ADMIN_GROUP_CREATE", parentId: 2    },
    {   id:168,   name: "HELP_EDIT"         }
]

function makeTreeFromArray(list) {
  const treeArray = [];
  const treeMap = {};
  
  //this loop generates the treeMap
  //and adds a .children prop to each item in the list:
  list.forEach((item, index) => {
    treeMap[item.id] = index;
    // list[index].children = [];
    item.children = [];
  });
  //Output of that function:
  //it maps ids to index in the list
  /*
  treeMap = {
    "1": 0,
    "2": 1,
    "3": 2,
    "168": 3
  }
  */
  
  //this loop pushes each child to its parent in the original list (if it has a parentId)
  //and it does this using the treeMap (essentially a lookup of ids to indexes).
  //if the child does not have a parent, then it is the highest level parent
  //in this case, push it to our output treeArray (with all its children):
  list.forEach(item => {
    if (item.parentId) {
      list[treeMap[item.parentId]].children.push(item);
    } else {
      treeArray.push(item);
    }
  });

  //console.log('treeMap', treeMap);
  //console.log('list', list);
  return treeArray;
}

const newArr = makeTreeFromArray(a);
console.log(newArr);

It works because, if you create pointers/references (copies of the original pointer), you can update the original item either by the original pointer or the new copies. Here is a trivial example:

See how you can change the original data with either variable (again important that we are working with objects, with primitives, it would not be the same).

(NOTE: JavaScript is garbage collected, so whenever all pointers to memory on the heap go out of scope, then the data is cleaned up. JavaScript makes handling memory "easy" by default but as you get deeper into what it is doing it becomes more complex. Lower level languages like C++ or Rust make you manage memory yourself - but Rust helps you with that with the compiler, with C++ you are basically on your own and can cause issues)

//original is a pointer to a location on the heap, where the object lives:
const original = {id: 1, children: []};

//pointerToOriginal is just a copy of the original pointer,
//so now they both point to the same location on the heap:
const pointerToOriginal = original;

//I can use either pointer, to change the object on the heap:
pointerToOriginal.id +=1;

//and it can be seen with both pointers (as they point to the same object):
console.log(pointerToOriginal, original);

//I can use either pointer, to change the object on the heap:
original.id +=1;

//and it can be seen with both pointers (as they point to the same object):
console.log(pointerToOriginal, original);

//Finally, we can see that the objects are equal
//and by default JavaScript just compares the memory addresses of each pointer:
console.log(pointerToOriginal == original); //true

If you want to make real copies, you need to do that. For "flat" objects, that only have primitive data you can do this like this (with spread operator). For nested objects and/or those that have Objects as their values, this won't work perfectly out of the box, because it creates only a "shallow copy" but we could create a deep copy function (but that's a long discussion):

//original is a pointer to a location on the heap, where the object lives:
const original = {id: 1, children: []};

//pointerToOriginal is now a new pointer to a shallow copy of the original object,
//so now they both point to DIFFERENT locations on the heap:
const pointerToNewCopy = {...original};

//Each pointer now only updates its Object on the heap:
pointerToNewCopy.id +=1;

//we see the orignal is un-changed:
console.log(pointerToNewCopy, original);

//Each pointer now only updates its Object on the heap:
original.id +=1;

//we see the pointerToNewCopy is un-changed:
console.log(pointerToNewCopy, original);

//Finally, we can see that the objects are not equal (even though all props are the same)
//this is because by default JavaScript just compares the memory addresses of each pointer:
console.log(pointerToNewCopy == original); //false

Important that we were working with objects above, with primitives, it would not be the same:

//primitive example:

let original = 5;
let copy = original;

//only the copy changes:
copy +=1;
console.log(copy, original);

//only the original changes:
original +=1;
console.log(copy, original);

If you console.log(list) from the last line before the return statement in your makeTreeFromArray(list) function (or you can call it outside after the function has run as it mutated the original list) you will see the following (in the console for this snippet, google chrome console does not inform you that there are pointer/reference copies). Important to note is that the children of id=1 are reference copies of the original items in that list (ref4 and ref6):

This is how the tree is built, from this mutated original list. Hope that now makes sense? It's a non-trivial topic.

list = [
  {
    "id": 1,
    "name": "ADMINISTRATION",
    "children": [
      {
        /**id:4**/
        "id": 2,
        "name": "ADMIN_GROUP",
        "parentId": 1,
        "children": [
          {
            /**id:6**/
            "id": 3,
            "name": "ADMIN_GROUP_CREATE",
            "parentId": 2,
            "children": []
          }
        ]
      }
    ]
  },
  /**ref:4**/,
  /**ref:6**/,
  {
    "id": 168,
    "name": "HELP_EDIT",
    "children": []
  }
]