Dynamically convert an array to a tree structure

Question

Can someone show me the most efficient way to convert an array to a tree structure?

var array= [
        {id: "1",     name: "header1"},
        {id: "2",     name: "header2"},
        {id: "1.1",   name: "subheader1.1"},
        {id: "1.2",   name: "subheader1.2"},
        {id: "2.1",   name: "subheader2.1"},
        {id: "2.2",   name: "subheader2.2"},
        {id: "1.1.1", name: "subheader1detail1"},
        {id: "2.1.1", name: "subheader2detail2"}
];

The resulting array should be like this:

var array = [{
    id: "1",
    name: "header1",
    items: [{
        id: "1.1",
        name: "subheader1.1",
        items: [{
            id: "1.1.1",
            name: "subheader1detail1",
        }]
    }, {
        id: "1.2",
        name: "subheader1.2"
    }]
}, {
    id: "2",
    name: "header2",
    items: [{
        id: "2.1",
        name: "subheader2.1",
        items: [{
            id: "2.1.1",
            name: "subheader2detail2",
        }]
    }, {
        id: "2.2",
        name: "subheader2.2"
    }]
}]

Thanks in advance

Answer 1

You can use a tree and build a nested array. This offer needs a sorted list.

Basically, it looks for the parent element of the node, and if the node has no parent, then the root of the node is found and inserted into the result array. If a parent is found, the actual node is inserted into the itemsparent property .

var array = [{ id: "1", name: "header1" }, { id: "2", name: "header2" }, { id: "1.1", name: "subheader1.1" }, { id: "1.2", name: "subheader1.2" }, { id: "2.1", name: "subheader2.1" }, { id: "2.2", name: "subheader2.2" }, { id: "1.1.1", name: "subheader1detail1" }, { id: "2.1.1", name: "subheader2detail2" }],
    result = [];

array.forEach(function (a) {
    var parent = a.id.split('.').slice(0, -1).join('.');

    this[a.id] = { id: a.id, name: a.name };
    if (parent) {
        this[parent] = this[parent] || {};
        this[parent].items = this[parent].items || [];
        this[parent].items.push(this[a.id]);
    } else {
        result.push(this[a.id]);
    }
}, {});

console.log(result);

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

Run codeHide result

Answer 2

You can try something like this:

,

var array= [
  {id: "1",     name: "header1"},
  {id: "2",     name: "header2"},
  {id: "1.1",   name: "subheader1.1"},
  {id: "1.2",   name: "subheader1.2"},
  {id: "2.1",   name: "subheader2.1"},
  {id: "2.2",   name: "subheader2.2"},
  {id: "1.1.1", name: "subheader1detail1"},
  {id: "2.1.1", name: "subheader2detail2"},
];

var result = {};

// Sort in case values are not in order. 
// This is to ensure parent is rendered before child
array.sort(function(a, b) {
  return a.id > b.id ? 1 : a.id - b.id ? -1 : 0
})
// Loop over sorted array to parse
.forEach(function(el) {
  // Check if element does not exists to prevent duplicate
  if (!result[el.id]) {
    // if parent, push it
    if (el.id.indexOf('.') === -1)
      result[el.id] = el;
    // If child, compute depth and search object to push to
    else {
      var ids = el.id.split('.');
      var _id = '';
      // temp variable to hold position to push
      var r = result[ids[0]];
      for (var i = 1; i < ids.length; i++) {
        // Compute the object id
        _id = (_id ? _id + '.' : _id) + ids[i - 1];
        // initialize items
        r.items = r.items || [];
        // search in items to get object if exist
        var o = r.items.find(x => x.id === _id);
        // if object exists, assign it to temp variable
        // If not, push to parent
        if (o) r = o;
      }
      if (r) {
        r.items = r.items || [];
        r.items.push(el);
      }
    }
  }
})

console.log(result)

Hide result

.

Answer 3

- Array.prototype.reduce hash table - . !

var array=[{id:"2",name:"header2"},{id:"1",name:"header1"},{id:"1.1",name:"subheader1.1"},{id:"1.2",name:"subheader1.2"},{id:"2.2",name:"subheader2.2"},{id:"2.1",name:"subheader2.1"},{id:"1.1.1",name:"subheader1detail1"},{id:"2.1.1",name:"subheader2detail2"}];

var result = array.sort(function(a,b) {
  return a.id - b.id;
}).reduce(function(hash) {
  return function(prev, curr) {
    var keys = curr.id.split('.');
    hash[curr.id] = hash[curr.id] || {};
    hash[curr.id] = {id: curr.id,name: curr.name};
    if (keys && keys.length > 1) {
      keys.pop();
      var key = keys.join('.');
      hash[key].items = hash[key].items || [];
      hash[key].items.push(hash[curr.id]);
    } else {
      prev.push(hash[curr.id]);
    }
    return prev;
  };
}(Object.create(null)), []);

console.log(result);

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

Hide result