How to create hierarchical HTML structure from flat JavaScript array?

Question

I have been asked to create a stock list using a hierarchal system with parent ID's. I'm having trouble displaying children under their parents. I know I need to use a recursive function of some kind but my brain just won't let me work out how it would go together to accommodate for infinite amounts of indenting.

Example JavaScript data...

[
    {id: 1, parent_id: null, title: "Row 1"},
    {id: 2, parent_id: 1, title: "Row 2"},
    {id: 3, parent_id: 2, title: "Row 3"},
    {id: 4, parent_id: 2, title: "Row 4"}
]

Which the HTML should to look like...

• Row 1
  • Row 2
    • Row 3
    • Row 4

If anyone could help me it would be awesome as I've been stuck on this for almost 4 hours and I can't find anything that is relevant to my specific goal.

Answer 1

Heads up: This requires your data to be ordered in a way that parent nodes appear before children reference them. A sort could be done first, if required.

Edit: a no-sort solution is posted below

Here's a way to do it using Array.prototype.reduce.

var arr = [
  {id: 1, parent_id: null, title: "Row 1"},
  {id: 2, parent_id: 1, title: "Row 2"},
  {id: 3, parent_id: 2, title: "Row 3"},
  {id: 4, parent_id: 2, title: "Row 4"}
];

var x = arr.reduce(function(map, node) {
  map.i[node.id] = node;
  node.children = [];
  node.parent_id === null ?
    map.result.push(node) :
    map.i[node.parent_id].children.push(node);
  return map;
}, {i:{}, result:[]}).result;

Explanation. I'll step through the reduce process I used

1. initialize the reduce with {i:{}, result:[]}

   We'll use the i object as a means of referencing parent nodes and the result array to store top-level root nodes

2. index each node by id using map.i[node.id] = node

3. If the node is a root node (parent_id === null), add it to the result with map.result.push(node)

4. If the node is a child node (parent_id !== null), add it to the children array of the parent node with map.index[node.parent_id].children.push(node)

---

Okay, let's check if it worked

// all root nodes
// see output below
console.log(JSON.stringify(x, null, "  "));

// first "root" node
console.log(x[0].id); //=> 1

// first child of first root node
console.log(x[0].children[0].id); //=> 2

// first child of first child of first root node
console.log(x[0].children[0].children[0].id); //=> 3

// second child of first child of first root node
console.log(x[0].children[0].children[1].id); //=> 4

All root nodes output

[
  {
    "id": 1,
    "parent_id": null,
    "title": "Row 1",
    "children": [
      {
        "id": 2,
        "parent_id": 1,
        "title": "Row 2",
        "children": [
          {
            "id": 3,
            "parent_id": 2,
            "title": "Row 3",
            "children": []
          },
          {
            "id": 4,
            "parent_id": 2,
            "title": "Row 4",
            "children": []
          }
        ]
      }
    ]
  }
]

---

If your initial data is unsorted...

The reduce method is a little more difficult in this case. Admittedly, pretty much all elegance is lost with this solution, but I've provided it to show it's still possible.

// this works on arbitrarily sorted data
var x = arr.reduce(function(map, node) {
  map.i[node.id] = node;
  node.children = [];
  if (node.parent_id === null) {
    map.result.push(node);
  }
  else if (node.parent_id in map.i) {
    map.i[node.parent_id].children.push(node);
  }
  else {
    (node.parent_id in map.cache) ?
      map.cache[node.parent_id].push(node) :
      map.cache[node.parent_id] = [node];
  }
  if (node.id in map.cache) {
    node.children = node.children.concat(map.cache[node.id]);
    delete map.cache[node.id];
  }
  return map;
}, {i:{}, cache:{}, result:[]}).result;

Answer 2

Inspired by Naomik, the code will fail when the parent_ids aren't in the correct position. Added a sorting function that will set them in the correct order.

obj = [
    {id: 2, parent_id: 1, title: "Row 2"},
    {id: 3, parent_id: 2, title: "Row 3"},
    {id: 4, parent_id: 2, title: "Row 4"},
    {id: 1, parent_id: null, title: "Row 1"}
]

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

var tree = document.getElementById("tree");
for (var i = 0; i < obj.length; ++i)
  {

    if (obj[i].parent_id == null)
      {
        createTreeElement("li", obj[i].id, obj[i].title, tree);
      }
    else
      {
         var treeChildNode = document.getElementById("t" + obj[i].parent_id).getElementsByTagName("ul");
        if (treeChildNode.length)
          {
            createTreeElement("li", obj[i].id, obj[i].title, treeChildNode[0]);
          }
        else
          {
            createTreeElement("ul", obj[i].parentId, "", document.getElementById("t" + obj[i].parent_id));
            createTreeElement("li", obj[i].id, obj[i].title, document.getElementById("t" + obj[i].parent_id).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>

This code is just a prove of concept in HTML to @Daniel Weiners answer why recursion isn't needed here based upon the object model.

Answer 3

You use an object that keeps track of your id's. For example:

var idObj = {};
var root = null;

// first populate the object with elements
for (var i = 0; i < arr.length; i++) {
  var item = arr[i];
  idObj[item.id] = item;
}

// then attach the children to the parents
for (var i = 0; i < arr.length; i++) {
  var item = arr[i];
  var parent = idObj[item.parent_id];
  if (parent) {
    parent.children = parent.children || [];
    parent.children.push(item);
  } else if (item.parent_id === null) { 
    //set the item as root if it has no parents
    root = item;
  }
}

This will add a children property to all those items.

Note: this solution is not recursive, but you can traverse the tree recursively starting from the root variable.