How to make a tree of objects from an array?

Question

JavaScript

There is an array of data:

const arr = [
    { uid: '110', parentUID: '3' },
    { uid: '120', parentUID: '3' },
    { uid: '2', parentUID: '5' },
    { uid: '12', parentUID: '11'  },
    { uid: '1', parentUID: '5' },
    { uid: '11', parentUID: null },
    { uid: '3', parentUID: '5' },
    { uid: '4', parentUID: '5' },
    { uid: '6', parentUID: '5' },
    { uid: '7', parentUID: '5' },
    { uid: '13', parentUID: '11' },
    { uid: '8', parentUID: '5' },
    { uid: '100', parentUID: '3' },
    { uid: '101', parentUID: '3' },
    { uid: '102', parentUID: '3' },
    { uid: '103', parentUID: '3' },
    { uid: '5', parentUID: null },
];

from this array you need to turn into a tree (example):

const obj = {
'5': { 
        uid: '5', 
        parentUID: null, 
        children: {
            "3": {
                uid: '3', 
                parentUID: '5',
                children: {
                    '110': { uid: '110', parentUID: '3' }
                    .....
                }
            },
            ......
        } 
},
};

Answer 1

function createTreeFromArray(arr, key, parentKey) {
  const tree = Object.fromEntries(arr.map(n => [ n[key], { ...n } ]));
  return Object.fromEntries(Object
    .entries(tree)
    .filter(([ , n ]) => !(tree[n[parentKey]] && ((tree[n[parentKey]].children ??= {})[n[key]] = n)))
  );
}


const tree = createTreeFromArray(arr, 'uid', 'parentUID');

Answer 2

Not a JS specialist, but it looks like there can be done easier than the standard graph traversal in width / depth.
Get a map of the objects that you will collect. The keys will be IDs, and the values ​​will be objects. For the objects, fill in the uid, parentUID, empty Map children, and empty children_list. Also remember somewhere id, which has null father.
Then, one more pass through the list of all elements, fill in the children_list of all objects in the Map from the previous step (put the current id in the list for parentUID).
Then, with one more pass through all the elements of this Map, collect the tree: bypass the list of children and put 'id' => object from the external Map at the given key in Map children. After the pass, children_list can be deleted.
If I understand correctly how JS works, then you will not copy the object, but its link. As a result, Map will contain all subtrees that refer to each other. You can then pull out the object from there by the key id of the root and delete the Map.