Open in app

Sign in

Write

Sign in

Building a hierarchical tree from a flat list: an easy-to-understand solution & visualisation

Selina Li
9 min readJan 9, 2020

--

Visualization of the input data, using dabeng org chart as library
tree visualisation of the output

I came across the problem of “how to build a hierarchical tree from a flat list” and viewed some solutions online including the stack overflow one https://stackoverflow.com/questions/12831746/javascript-building-a-hierarchical-tree.

There is one solution online I found particularly easy to understand and a good point to start with (not the best performing though).

I found the online solution here, authored by Alexandru Pausan : https://jsfiddle.net/alexandrupausan/qjxpLhfu/

I will use this article to go through the solution step by step. (Note: for better understanding I modified the original solution).

The Solution

Input:

var items = [ 
{"Id": "1", "Name": "abc", "Parent": "2"}, 
{"Id": "2", "Name": "abc", "Parent": ""}, 
{"Id": "3", "Name": "abc", "Parent": "5"}, 
{"Id": "4", "Name": "abc", "Parent": "2"}, 
{"Id": "5", "Name": "abc", "Parent": ""}, 
{"Id": "6", "Name": "abc", "Parent": "2"}, 
{"Id": "7", "Name": "abc", "Parent": "6"}, 
{"Id": "8", "Name": "abc", "Parent": "6"} 
];

Expected output:

[
 {
  "Id": "2",
  "Name": "abc",
  "Parent": "",
  "children": [
   {
    "Id": "1",
    "Name": "abc",
    "Parent": "2",
    "children": []
   },
   {
    "Id": "4",
    "Name": "abc",
    "Parent": "2",
    "children": []
   },
   {
    "Id": "6",
    "Name": "abc",
    "Parent": "2",
    "children": [
     {
      "Id": "7",
      "Name": "abc",
      "Parent": "6",
      "children": []
     },
     {
      "Id": "8",
      "Name": "abc",
      "Parent": "6",
      "children": []
     }
    ]
   }
  ]
 },
 {
  "Id": "5",
  "Name": "abc",
  "Parent": "",
  "children": [
   {
    "Id": "3",
    "Name": "abc",
    "Parent": "5",
    "children": []
   }
  ]
 }
]

Complete code (you may try this is jsfiddle):

var items = [ 
  {"Id": "1", "Name": "abc", "Parent": "2"}, 
  {"Id": "2", "Name": "abc", "Parent": ""}, 
  {"Id": "3", "Name": "abc", "Parent": "5"}, 
  {"Id": "4", "Name": "abc", "Parent": "2"}, 
  {"Id": "5", "Name": "abc", "Parent": ""}, 
  {"Id": "6", "Name": "abc", "Parent": "2"}, 
  {"Id": "7", "Name": "abc", "Parent": "6"}, 
  {"Id": "8", "Name": "abc", "Parent": "6"} 
];function unflatten(items) {
  var tree = [],
      mappedArr = {}
      
  // Build a hash table and map items to objects
  items.forEach(function(item) {
    var id = item.Id;
    if (!mappedArr.hasOwnProperty(id)) { // in case of duplicates
      mappedArr[id] = item; // the extracted id as key, and the item as value
      mappedArr[id].children = [];  // under each item, add a key "children" with an empty array as value
    }
  })
  
  // Loop over hash table
  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. Note this will continue till we have only root level elements left
      if (mappedElem.Parent) { 
        var parentId = mappedElem.Parent;
        mappedArr[parentId].children.push(mappedElem); 
      }
      
      // If the element is at the root level, directly push to the tree
      else { 
        tree.push(mappedElem);
      } 
    }
  }
  
  return tree;
  
}var result = unflatten(items);document.body.innerHTML = "<pre>" + (JSON.stringify(result, null, " "))

Step by Step

Now we will go step by step and make it very clear.

Step 1: Build a hash table with Id as key and the item itself as value, creating a “children” attribute for each item

Loop over items:

function unflatten(items) {
  var tree = [],
      mappedArr = {}
      
  // Loop over items
  items.forEach(function(item) {
    ...
  
}

Create a hash table with each item id as the key, and the item itself as the value:

...
    var id = item.Id; 
    if (!mappedArr.hasOwnProperty(id)) { // in case of duplicates
      mappedArr[id] = item; // the extracted id as key, and the item as value
      ...
    }
...

Also under each item, add a key “children” with an empty array as value:

...
      mappedArr[id].children = []; 
...

Code we have so far:

var items = [ 
  {"Id": "1", "Name": "abc", "Parent": "2"}, 
  {"Id": "2", "Name": "abc", "Parent": ""}, 
  {"Id": "3", "Name": "abc", "Parent": "5"}, 
  {"Id": "4", "Name": "abc", "Parent": "2"}, 
  {"Id": "5", "Name": "abc", "Parent": ""}, 
  {"Id": "6", "Name": "abc", "Parent": "2"}, 
  {"Id": "7", "Name": "abc", "Parent": "6"}, 
  {"Id": "8", "Name": "abc", "Parent": "6"} 
];function unflatten(items) {
  var tree = [],
      mappedArr = {}
      
  // Build a hash table and map items to objects
  items.forEach(function(item) {
    var id = item.Id;
    if (!mappedArr.hasOwnProperty(id)) { // in case of duplicates
      mappedArr[id] = item; // the extracted id as key, and the item as value
      mappedArr[id].children = [];  // under each item, add a key "children" with an empty array as value
    }
  })
  
  return mappedArr;
  
}var result = unflatten(items);document.body.innerHTML = "<pre>" + (JSON.stringify(result, null, " "))

Output so far:

Id as key allows us to easily query each item as an object by its id.

children as attributes prepares for the next step.

{
 "1": {
  "Id": "1",
  "Name": "abc",
  "Parent": "2",
  "children": []
 },
 "2": {
  "Id": "2",
  "Name": "abc",
  "Parent": "",
  "children": []
 },
 "3": {
  "Id": "3",
  "Name": "abc",
  "Parent": "5",
  "children": []
 },
 "4": {
  "Id": "4",
  "Name": "abc",
  "Parent": "2",
  "children": []
 },
 "5": {
  "Id": "5",
  "Name": "abc",
  "Parent": "",
  "children": []
 },
 "6": {
  "Id": "6",
  "Name": "abc",
  "Parent": "2",
  "children": []
 },
 "7": {
  "Id": "7",
  "Name": "abc",
  "Parent": "6",
  "children": []
 },
 "8": {
  "Id": "8",
  "Name": "abc",
  "Parent": "6",
  "children": []
 }
}

Step 2: Find parent -> go to parent -> add the item as parent’s child

What we have done in step 1 allows us to easily query the object with its id — what we can do next is basically “find my parent -> go to my parent -> add myself as my parent’s child”.

Loop over elements of the hash table created in step 1:

  // Loop over hash table
  for (var id in mappedArr) { 
    if (mappedArr.hasOwnProperty(id)) {
      ...
    }
  }

If the element is NOT at ROOT level (i.e. the element has Parent):

  • Get the parent id of the element
  • Use parent id to locate the corresponding parent element in our hash table
  • Push the element to ‘children’ array of the parent element
  • The same process will continue until we have only root-level elements left
...      // If the element is not at the root level, add it to its parent array of children. Note this will continue till we have only root-level elements left       if (mappedElem.Parent) { // obtain the element's parent id 
        var parentId = mappedElem.Parent;// locate the parent item in the hash table, and push the element to its children array
        mappedArr[parentId].children.push(mappedElem);  
      
      }
...

Here is the trick:

The above process will continue until we have only root-level elements (i.e. the elements that have no Parent) left.

At this time, the root-level elements should have collected all of their own children.

We can push them to the tree directly.

...
      // If the element is at the root level, directly push to the tree
      else { 
        tree.push(mappedElem);
      } 
...

Code so far (already complete):

var items = [ 
  {"Id": "1", "Name": "abc", "Parent": "2"}, 
  {"Id": "2", "Name": "abc", "Parent": ""}, 
  {"Id": "3", "Name": "abc", "Parent": "5"}, 
  {"Id": "4", "Name": "abc", "Parent": "2"}, 
  {"Id": "5", "Name": "abc", "Parent": ""}, 
  {"Id": "6", "Name": "abc", "Parent": "2"}, 
  {"Id": "7", "Name": "abc", "Parent": "6"}, 
  {"Id": "8", "Name": "abc", "Parent": "6"} 
];function unflatten(items) {
  var tree = [],
      mappedArr = {}
      
  // Build a hash table and map items to objects
  items.forEach(function(item) {
    var id = item.Id;
    if (!mappedArr.hasOwnProperty(id)) { // in case of duplicates
      mappedArr[id] = item; // the extracted id as key, and the item as value
      mappedArr[id].children = [];  // under each item, add a key "children" with an empty array as value
    }
  })
  
  // Loop over hash table
  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. Note this will continue till we have only root level elements left
      if (mappedElem.Parent) { 
        var parentId = mappedElem.Parent;
        mappedArr[parentId].children.push(mappedElem); 
      }
      
      // If the element is at the root level, directly push to the tree
      else { 
        tree.push(mappedElem);
      } 
    }
  }
  
  return tree;
  
}var result = unflatten(items);document.body.innerHTML = "<pre>" + (JSON.stringify(result, null, " "))

Output:

[
 {
  "Id": "2",
  "Name": "abc",
  "Parent": "",
  "children": [
   {
    "Id": "1",
    "Name": "abc",
    "Parent": "2",
    "children": []
   },
   {
    "Id": "4",
    "Name": "abc",
    "Parent": "2",
    "children": []
   },
   {
    "Id": "6",
    "Name": "abc",
    "Parent": "2",
    "children": [
     {
      "Id": "7",
      "Name": "abc",
      "Parent": "6",
      "children": []
     },
     {
      "Id": "8",
      "Name": "abc",
      "Parent": "6",
      "children": []
     }
    ]
   }
  ]
 },
 {
  "Id": "5",
  "Name": "abc",
  "Parent": "",
  "children": [
   {
    "Id": "3",
    "Name": "abc",
    "Parent": "5",
    "children": []
   }
  ]
 }
]

What if NO root-level items in input data?

Assume our data removes the lines for the root-level items:

{"Id": "2", "Name": "abc", "Parent": ""},
{"Id": "5", "Name": "abc", "Parent": ""}

Our input will look like this:

var items = [ 
  {"Id": "1", "Name": "abc", "Parent": "2"}, 
  {"Id": "3", "Name": "abc", "Parent": "5"}, 
  {"Id": "4", "Name": "abc", "Parent": "2"}, 
  {"Id": "6", "Name": "abc", "Parent": "2"}, 
  {"Id": "7", "Name": "abc", "Parent": "6"}, 
  {"Id": "8", "Name": "abc", "Parent": "6"} 
];

This will usually happen in real case.

In this case, the above code will fail to generate results.

Thus when building the hash table, we need to add one more step between step 1 and step 2, to create an object for root-level items (“2” and “5”)

  // If root-level items are not included in hash table, include them
  items.forEach(function(item) {
    var parentId = item.Parent;
    if (!mappedArr.hasOwnProperty(parentId)) {
      // make up an item for root-level node
      newItem = {};
      newItem.Id = parentId;
      newItem.Name = 'abc';
      newItem.Parent = '';
      mappedArr[parentId] = newItem; // the parent id as key, and made-up an item as value
      mappedArr[parentId].children = []; 
    }
  })

Complete code:

var items = [ 
  {"Id": "1", "Name": "abc", "Parent": "2"}, 
  {"Id": "3", "Name": "abc", "Parent": "5"}, 
  {"Id": "4", "Name": "abc", "Parent": "2"}, 
  {"Id": "6", "Name": "abc", "Parent": "2"}, 
  {"Id": "7", "Name": "abc", "Parent": "6"}, 
  {"Id": "8", "Name": "abc", "Parent": "6"} 
];function unflatten(items) {
  var tree = [],
      mappedArr = {}
      
  // Build a hash table and map items to objects
  items.forEach(function(item) {
    var id = item.Id;
    if (!mappedArr.hasOwnProperty(id)) { // in case of duplicates
      mappedArr[id] = item; // the extracted id as key, and the item as value
      mappedArr[id].children = [];  // under each item, add a key "children" with an empty array as value
    }
  })
  
  // If root-level nodes are not included in hash table, include them
  items.forEach(function(item) {
    var parentId = item.Parent;
    if (!mappedArr.hasOwnProperty(parentId)) {
      // make up an item for root-level node
      newItem = {};
      newItem.Id = parentId;
      newItem.Name = 'abc';
      newItem.Parent = '';
      mappedArr[parentId] = newItem; // the parent id as key, and made-up an item as value
      mappedArr[parentId].children = []; 
    }
  })
  
  // Loop over hash table
  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. Note this will continue till we have only root level elements left
      if (mappedElem.Parent) { 
        var parentId = mappedElem.Parent;
        mappedArr[parentId].children.push(mappedElem); 
      }
      
      // If the element is at the root level, directly push to the tree
      else { 
        tree.push(mappedElem);
      } 
    }
  }
  
  return tree;
  
}var result = unflatten(items);document.body.innerHTML = "<pre>" + (JSON.stringify(result, null, " "))

And the output will be the same.

Of course we can do a lot to improve the performance of the code - here is just the basic logic.

Can I visualise the tree?

Yes and I do this by using dabeng org chart library:

dabeng/OrgChart

It's a simple and direct organization chart plugin. Anytime you want a tree-like chart, you can turn to OrgChart. …

github.com

This is a handy library to visualize tree structure.

Here is the result:

Visualization of the input data, using dabeng org chart as library

Note: dabeng org chart supports one root node so I added “mychart” to be my only root node.

Another way to do this is using Google org chart:

Organization Chart | Charts | Google Developers

Edit description

developers.google.com

And here is how it looks like:

JavaScript
Org Charts
Trees

--

--

Selina Li

Written by Selina Li

131 Followers

Technical Lead, Data Product Development, Officeworks, https://www.linkedin.com/in/selina-zhuohang-li-3b7355120/

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams