How to build a tree of objects out of a flat array of records in JavaScript?

Question

How do I implement this properly?

const tree = buildTree(1, shuffleArray([
  { type: 'string', source_id: 1, name: 'foo', value: 'asdf' },
  { type: 'integer', source_id: 1, name: 'bar', value: 123 },
  { type: 'object', source_id: 1, name: 'nested', value: 2 },
  { type: 'object', source_id: 2, name: 'nested', value: 3, array: true },
  { type: 'boolean', source_id: 3, name: 'random', value: true },
  { type: 'string', source_id: 3, name: 'another', value: 'hello' },
  { type: 'object', source_id: 2, name: 'nested', value: 4, array: true },
  { type: 'boolean', source_id: 4, name: 'random', value: false },
  { type: 'string', source_id: 4, name: 'another', value: 'world' },
  { type: 'object', source_id: 2, name: 'nested', value: 5, array: true },
  { type: 'boolean', source_id: 5, name: 'random', value: true },
  { type: 'string', source_id: 5, name: 'another', value: 'awesome' },
]))

function buildTree(startId, array) {
  const map = array.reduce((m, x) => {
    m[x.source_id] = m[x.source_id] ?? {}
    if (x.array) {
      m[x.source_id][x.name] = m[x.source_id][x.name] ?? []
      m[x.source_id][x.name].push({ id: x.value })
    } else {
      m[x.source_id][x.name] = x.value
    }
    return m
  }, {})

  // ??? getting lost...
}

function shuffleArray(array) {
  for (var i = array.length - 1; i > 0; i--) {
      var j = Math.floor(Math.random() * (i + 1));
      var temp = array[i];
      array[i] = array[j];
      array[j] = temp;
  }
  return array
}

where the "expected tree" would be something like this:

const expectedTree = {
  id: 1,
  foo: 'asdf',
  bar: 123,
  nested: {
    id: 2,
    nested: [
      {
        id: 3,
        random: true,
        another: 'hello'
      },
      {
        id: 4,
        random: false,
        another: 'world'
      },
      {
        id: 5,
        random: true,
        another: 'awesome'
      }
    ]
  }
}

The shuffleArray is just to show that the records could be in any order, and the id (source_id) property is not necessarily in incremental order (actually in my case they are UUIDs with the hierarchy not really in any particular order). Each "record" in buildTree is a "property" record basically like this:

create table object_properties {
  uuid id;
  uuid source_id; // the object which has this property
  string name; // the property name
  uuid value; // the property value object
}

// ...and same for boolean, integer, etc. properties
create table string_properties {
  uuid id;
  uuid source_id; // the object which has this property
  string name; // the property name
  string value; // the property value string
}

In my buildTree I can kind of imagine creating a map from the source_id (the base object node which has property name), to the names, to the values. But then maybe iterating over the source IDs, looking for objects nested inside the name values, and converting them to objects instead of just IDs. But this is getting hard to comprehend and I'm sure there is an easier way somehow.

What is an algorithm to build an "object tree" from this flat list of records?

In my situation, I am fetching a bunch of deeply nested property objects, recursively, and need to stitch back together an object tree out of them.

Answer 1

It looks like the name "nested" plays a special role. When it occurs, the corresponding value property does not hold a literal value to assign to the named property (as is the case with other names), but is a reference to an existing source_id value.

This means your code needs to deal with that name specifically and then establish the parent-child relationship. This relationship is further influenced by the array property.

I would define buildTree as follows, making use of a Map, which is built first using its constructor argument:

function buildTree(startId, arr) {
    const map = new Map(arr.map(({source_id}) => [source_id, { id: source_id }]));
    for (const {source_id, name, value, array} of arr) {
        if (name !== "nested") {
            map.get(source_id)[name] = value;
        } else if (array) {
            (map.get(source_id).nested ??= []).push(map.get(value));
        } else {
            map.get(source_id).nested = map.get(value);
        }
    }
    return map.get(startId);
}

// Code below has not changed
function shuffleArray(array) { for (var i = array.length - 1, j, temp; i > 0; i--) {j = Math.floor(Math.random() * (i + 1));temp = array[i];array[i] = array[j];array[j] = temp;} return array;}
const tree = buildTree(1, shuffleArray([{ type: 'string', source_id: 1, name: 'foo', value: 'asdf' },{ type: 'integer', source_id: 1, name: 'bar', value: 123 },{ type: 'object', source_id: 1, name: 'nested', value: 2 },{ type: 'object', source_id: 2, name: 'nested', value: 3, array: true },{ type: 'boolean', source_id: 3, name: 'random', value: true },{ type: 'string', source_id: 3, name: 'another', value: 'hello' },{ type: 'object', source_id: 2, name: 'nested', value: 4, array: true },{ type: 'boolean', source_id: 4, name: 'random', value: false },{ type: 'string', source_id: 4, name: 'another', value: 'world' },{ type: 'object', source_id: 2, name: 'nested', value: 5, array: true },{ type: 'boolean', source_id: 5, name: 'random', value: true },{ type: 'string', source_id: 5, name: 'another', value: 'awesome' },]))
console.log(tree);

Note that the order in which objects are pushed into arrays is defined by the original order of the objects. Since this input array is shuffled, the output may show arrays in different ordering on separate runs. Something similar holds for object keys (see Object property order)

Answer 2

You should try Array.prototype.group(). Please refer below document. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/group

const inventory = [
      { name: 'asparagus', type: 'vegetables', quantity: 5 },
      { name: 'bananas',  type: 'fruit', quantity: 0 },
      { name: 'goat', type: 'meat', quantity: 23 },
      { name: 'cherries', type: 'fruit', quantity: 5 },
      { name: 'fish', type: 'meat', quantity: 22 }
    ];


const result = inventory.group(({ type }) => type);

/* Result is:
{
  vegetables: [
    { name: 'asparagus', type: 'vegetables', quantity: 5 },
  ],
  fruit: [
    { name: "bananas", type: "fruit", quantity: 0 },
    { name: "cherries", type: "fruit", quantity: 5 }
  ],
  meat: [
    { name: "goat", type: "meat", quantity: 23 },
    { name: "fish", type: "meat", quantity: 22 }
  ]
}
*/