build_tree.js

/*
Given a list of objects which form one or many trees, this function builds and returns these trees. Works in linear time.
*/
const idField = 'id';
const parentIdField = 'parent'

const buildTree = (objectList) => {

    let mainObjects = [];
    let objects = {};
    objectList.forEach((object) => {
        const id = object[idField];

        // Add the object in the dictionary if it isn't there already
        if (objects[id] === undefined) {
            objects[id] = object;
            object.rows = [];
        } else {
            // If it is there, update its properties
            object = Object.assign(objects[id], object);
        }
        const parentId = object[parentIdField];
        if (parentId != null) {
            // Add the parent object in the dictionary if it isn't there already
            if (objects[parentId] === undefined) {
                objects[parentId] = {
                    [idField]: parentId,
                    rows: [object]
                };
                // Else just update it
            } else {
                objects[parentId].rows.push(object);
            }
        } else {
            mainObjects.push(objects[id]);
        }
    });
    return mainObjects;
};
buildTree([
    { id:0, name:'root', parent: undefined },
    { id:1, name:'branch1', parent: 0 },
    { id:2, name:'branch2', parent: 0 },
    { id:3, name:'branch3', parent: 0 },
    { id:4, name:'branch3 subbranch 1', parent: 3},
    { id:5, name:'branch3 subbranch 2', parent: 3},

])

/*
Returns the following:
[{
  "id": 0,
  "name": "root",
  "rows": [
    {
      "id": 1,
      "name": "branch1",
      "parent": 0,
      "rows": []
    },
    {
      "id": 2,
      "name": "branch2",
      "parent": 0,
      "rows": []
    },
    {
      "id": 3,
      "name": "branch3",
      "parent": 0,
      "rows": [
        {
          "id": 4,
          "name": "branch3 subbranch 1",
          "parent": 3,
          "rows": []
        },
        {
          "id": 5,
          "name": "branch3 subbranch 2",
          "parent": 3,
          "rows": []
        }
      ]
    }
  ]
}]
*/