Building a tree array from flat array with parent and children nodes sorted by date (aka how to sort a discussion)

Question

There are many solutions for building a tree array from a flat array based on numeric reference IDs using JavaScript. But I couldn't find any solution for creating a tree array where sorting is based on alphanumeric IDs and date.

I have a number of discussion messages stored in a flat array (see below). I need to create a tree array from it, with all children sorted by date. This is so the whole discussion (which includes the initial message as well as replies to various messages in the discussion thread) is in the correct order of messages, as they were originally posted.

Here is an example of the array.

nodes = [
    {id: 'B', references: "A", date: "2020-12-30T11:00:01-01:00"},        
    {id: 'J', references: "F", date: "2020-12-30T11:00:06-01:00"},
    {id: 'D', references: "A", date: "2020-12-30T11:00:07-01:00"},
    {id: 'A', references: "", date: "2020-12-30T11:00:00-01:00"}, // initial post has no reference
    {id: 'E', references: "C", date: "2020-12-30T11:00:03-01:00"},
    {id: 'F', references: "E", date: "2020-12-30T11:00:04-01:00"},
    {id: 'C', references: "A", date: "2020-12-30T11:00:02-01:00"},
    {id: 'I', references: "G", date: "2020-12-30T11:00:09-01:00"},
    {id: 'G', references: "A", date: "2020-12-30T11:00:08-01:00"},
    {id: 'H', references: "G", date: "2020-12-30T11:00:09-02:00"},
    {id: 'K', references: "F", date: "2020-12-30T11:00:05-01:00"},
];

The goal is to print an ordered discussion tree visually, so it looks like this:

A
_ B
_ C
_ _ E
_ _ _ F
_ _ _ _ K
_ _ _ _ J
_ D
_ G
_ _ I
_ _ H

I am looking for a JavaScript solution.

UPDATE:

I found, that the following code, where all the entries in the array are pre-sorted by day, will create the proper tree:

let arr = [
{id: 'A', references: "", date: "2020-12-30T11:00:00-01:00"},
{id: 'B', references: "A", date: "2020-12-30T11:00:01-01:00"},
{id: 'C', references: "A", date: "2020-12-30T11:00:02-01:00"},
{id: 'E', references: "C", date: "2020-12-30T11:00:03-01:00"},
{id: 'F', references: "E", date: "2020-12-30T11:00:04-01:00"},
{id: 'K', references: "F", date: "2020-12-30T11:00:05-01:00"},
{id: 'J', references: "F", date: "2020-12-30T11:00:06-01:00"},
{id: 'D', references: "A", date: "2020-12-30T11:00:07-01:00"},
{id: 'G', references: "A", date: "2020-12-30T11:00:08-01:00"},
{id: 'I', references: "G", date: "2020-12-30T11:00:09-01:00"},
{id: 'H', references: "G", date: "2020-12-30T11:00:09-02:00"},
];

function unflatten(arr) {
var tree = [],
mappedArr = {},
arrElem,
mappedElem;

// First map the nodes of the array to an object -> create a hash table.
for(var i = 0, len = arr.length; i < len; i++) {
arrElem = arr[i];
mappedArr[arrElem.id] = arrElem;
mappedArr[arrElem.id]['children'] = [];
}


for (var id in mappedArr) {
if (mappedArr.hasOwnProperty(id)) {
mappedElem = mappedArr[id];
// If the element is not at the root level, add it to its parent array of children.
if (mappedElem.references) {
mappedArr[mappedElem['references']]['children'].push(mappedElem);
}
// If the element is at the root level, add it to first level elements array.
else {
tree.push(mappedElem);
}
}
}
return tree;
}

var tree = unflatten(arr);
console.log(tree);
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))

Result:

 [
 {
  "id": "A",
  "references": "",
  "date": "2020-12-30T11:00:00-01:00",
  "children": [
   {
    "id": "B",
    "references": "A",
    "date": "2020-12-30T11:00:01-01:00",
    "children": []
   },
   {
    "id": "C",
    "references": "A",
    "date": "2020-12-30T11:00:02-01:00",
    "children": [
     {
      "id": "E",
      "references": "C",
      "date": "2020-12-30T11:00:03-01:00",
      "children": [
       {
        "id": "F",
        "references": "E",
        "date": "2020-12-30T11:00:04-01:00",
        "children": [
         {
          "id": "K",
          "references": "F",
          "date": "2020-12-30T11:00:05-01:00",
          "children": []
         },
         {
          "id": "J",
          "references": "F",
          "date": "2020-12-30T11:00:06-01:00",
          "children": []
         }
        ]
       }
      ]
     }
    ]
   },
   {
    "id": "D",
    "references": "A",
    "date": "2020-12-30T11:00:07-01:00",
    "children": []
   },
   {
    "id": "G",
    "references": "A",
    "date": "2020-12-30T11:00:08-01:00",
    "children": [
     {
      "id": "I",
      "references": "G",
      "date": "2020-12-30T11:00:09-01:00",
      "children": []
     },
     {
      "id": "H",
      "references": "G",
      "date": "2020-12-30T11:00:09-02:00",
      "children": []
     }
    ]
   }
  ]
 }
]

https://jsfiddle.net/jarosciak/73xuk25q/3/

Any better ideas?

Answer 1

The following is the code I ended up using:

window.addEventListener('load', (event) => {

obj = [
{id: 'A', references: "", date: "2020-12-30T11:00:00-01:00", subject: "Title #1", body: "Message Body #1"},
{id: 'B', references: "A", date: "2020-12-30T11:00:01-01:00", subject: "Title #2", body: "Message Body #2"},
{id: 'C', references: "A", date: "2020-12-30T11:00:02-01:00", subject: "Title #3", body: "Message Body #3"},
{id: 'E', references: "C", date: "2020-12-30T11:00:03-01:00", subject: "Title #4", body: "Message Body #4"},
{id: 'F', references: "E", date: "2020-12-30T11:00:04-01:00", subject: "Title #5", body: "Message Body #5"},
{id: 'K', references: "F", date: "2020-12-30T11:00:05-01:00", subject: "Title #6", body: "Message Body #6"},
{id: 'J', references: "F", date: "2020-12-30T11:00:06-01:00", subject: "Title #7", body: "Message Body #7"},
{id: 'D', references: "A", date: "2020-12-30T11:00:07-01:00", subject: "Title #8", body: "Message Body #8"},
{id: 'G', references: "A", date: "2020-12-30T11:00:08-01:00", subject: "Title #9", body: "Message Body #9"},
{id: 'I', references: "G", date: "2020-12-30T11:00:09-01:00", subject: "Title #10", body: "Message Body #10"},
{id: 'H', references: "G", date: "2020-12-30T11:00:09-02:00", subject: "Title #11", body: "Message Body #11"},
]

obj.sort(function(a, b){
    return (a.references == null ? 0 : a.references) - (b.references == null ? 0 : b.references);
});

var tree = document.getElementById("tree");
for (var i = 0; i < obj.length; ++i)
  {
        var msg_draft = "<b>" + obj[i].id + "</b><br>" + obj[i].subject + "<br>(" + obj[i].date + ")<br>" + obj[i].body;
    if ((obj[i].references == null) || (obj[i].references == ""))
      {
        createTreeElement("li", obj[i].id, msg_draft , tree);
      }
    else
      {
         var treeChildNode = document.getElementById("t" + obj[i].references).getElementsByTagName("ul");
        if (treeChildNode.length)
          {
            createTreeElement("li", obj[i].id, msg_draft , treeChildNode[0]);
          }
        else
          {
            createTreeElement("ul", obj[i].references, "", document.getElementById("t" + obj[i].references));
            createTreeElement("li", obj[i].id, msg_draft , document.getElementById("t" + obj[i].references).getElementsByTagName("ul")[0]);
          }
      }
  }

function createTreeElement(name, id, text, parent)
{
  var node = document.createElement(name);
  node.id = "t" + id;
  node.innerHTML = text;
  parent.appendChild(node);
}
});

<ul id="tree"></ul>

Additionally, the result of sorting the flat array to a tree array; and its final HTML representation, if someone wants to play with it, can be seen in this JS Fiddle: https://jsfiddle.net/jarosciak/jd6hLvr4/