How to convert an array into a hierarchical array

Question

I have some data which is

var currentData = [
    {'ticket':'CAP', 'child':'CT-1'},
    {'ticket':'CAP', 'child':'CT-2'},
    {'ticket':'CT-1', 'child':'CT-1-A'},
    {'ticket':'CT-1', 'child':'CT-1-B'}
];

The data is flat and I need to convert it into something like:

{
    'ticket': 'CAP',
    children : [{
        'ticket' : 'CT-1',
        'children' : [{
            'ticket' : 'CT-1-A',
            'children' : []
        }, {
            'ticket' : 'CT-1-B',
            'children' : []
        }],
        [{
            'ticket' : 'CT-2',
            'children' : []
        }]
    }]
}

(I think the above is valid)?

I'm very lost as to how. I am going to show my effort but, I'm not sure if my approach is correct or not.

var currentData = [{'ticket':'cap', 'child':'CT-1'},{'ticket':'cap', 'child':'CT-2'}, {'ticket':'CT-1', 'child':'CT-1-A'},{'ticket':'CT-1', 'child':'CT-1-B'}];

var newList = [];
function convert(list){
    if (newList.length <= 0){
        var child = [];
        var emptyChild = [];
        child.push({'ticket': list[0].child, 'child': emptyChild });
        newList.push({'ticket': list[0].ticket, 'children' : child});
        list.splice(0,1);
    } // the if statement above works fine
    
    for(var i = 0;  i < list.length; i++) {
        var ticket = list[i].ticket;
        for(var j = 0; j < newList.length; j++) {
            if (newList[j].ticket == ticket){
                var child;
                var emptyChild = [];
                child = {'ticket': list[i].child, 'child': emptyChild };
                newList[j].children.push(child);
                list.splice(i,1);
                break;
            } // the if above works
            else{
                var child2 = getFromChildren(ticket, newList, list[i]); // child2 is Always null, even if getFromChildren returns an object
                newList[j].children.push(child2);
                list.splice(i,1);
                break;
            }
        }
    }   
    
    if (list.length > 0){
        convert(list);
    }
}

function getFromChildren(ticket, list, itemToAdd){

    if (list == null || list[0].children == null)
        return;
    
    for(var i = 0; i < list.length; i++) {
        if (list[i] == null)
        return;
        
        if (list[i].ticket == ticket){
            list[i].child.push(itemToAdd.child); // ** can't do this, javascript passes by value, not by reference :(
        } else{
            getFromChildren(ticket, list[i].children, itemToAdd);
        }
    }
}

convert(currentData);

I think I've made a mess of it. In the comments I've put a ** explaining that it isn't working due to JavaScript not passing by reference, however upon further reading I don't think that is correct as I'm passing the object which is by reference?

Edit

The data, shown with currentData will not always start at the root sadly either

Why one childless object has its `children` property set to `null` and the other set to an empty array `[]`. — ibrahim mahrir, Sep 15 '17 at 13:57
@ibrahimmahrir, a simple mistake on part, sorry. I've updated the question, but to be honest, it could be an empty array `[]` or `null`, either would be valid/acceptable — MyDaftQuestions, Sep 15 '17 at 13:58
what you want to convert your data to is not syntactically correct, i assume you forgot to add a `]}` at the end ? — doubleOrt, Sep 15 '17 at 14:10
@KoushikChatterjee, no, sadly it won't. I've updated my question — MyDaftQuestions, Sep 15 '17 at 14:14
@MyDaftQuestions the third child of the `children` property is just a value, with no property to refer to it; to see what i mean, just run the `children` property's value in a browser, a `SyntaxError` will be thrown (i am referring to the array that holds `CT-2`). — doubleOrt, Sep 15 '17 at 14:19
The error is still there, is this what you want your data to look like: `var obj = { 'ticket': 'CAP', children : [{ 'ticket' : 'CT-1', children : [{ 'ticket' : 'CT-1-A', 'children' : [] }, { 'ticket' : 'CT-1-B', 'children' : [] }] }, { 'ticket' : 'CT-2', children : [] } ] };` ? — doubleOrt, Sep 15 '17 at 14:25

ibrahim mahrir · Accepted Answer · 2017-09-15T14:38:18.310

function convert(arr) {
  var children = {};                                         // this object will hold a reference to all children arrays

  var res = arr.reduce(function(res, o) {                    // for each object o in the array arr
    if(!res[o.ticket]) {                                     // if there is no object for the element o.ticket
      res[o.ticket] = {ticket: o.ticket, children: []};      // then creates an object for it
      children[o.ticket] = res[o.ticket].children;           // and store a reference to its children array
    }
    if(!res[o.child]) {                                      // if there is no object for the element o.child
      res[o.child] = {ticket: o.child, children: []};        // then creates an object for it
      children[o.child] = res[o.child].children;             // and store a reference to its children array
    }
    return res;
  }, {});
  
  arr.forEach(function(o) {                                  // now for each object o in the array arr
    children[o.ticket].push(res[o.child]);                   // add the object of o.child (from res) to its children array
    delete res[o.child];                                     // and remove the child object from the object res
  });
  
  return res;
}



var currentData = [
    {'ticket':'CAP', 'child':'CT-1'},
    {'ticket':'CAP', 'child':'CT-2'},
    {'ticket':'CT-1', 'child':'CT-1-A'},
    {'ticket':'CT-1', 'child':'CT-1-B'}
];

console.log(convert(currentData));

Explanation:

The reduce part creates an object of the form: { ticket: "...", children: [] } for each element (child or not). So right after reduce, the object res will be:

res = {
    'CAP': { ticket: 'CAP', children: [] },
    'CT-1': { ticket: 'CT-1', children: [] },
    'CT-2': { ticket: 'CT-2', children: [] },
    'CT-1-A': { ticket: 'CT-1-A', children: [] },
    'CT-1-B': { ticket: 'CT-1-B', children: [] },
}

Now comes the forEach bit which loops over the array once more, and now for each object it fetches the object of .child from res above, push it into .ticket object's children (which a reference to it is stored in children object), then remove the .child object from the object res.

I need to learn/read up on the `reduce` function. This code is very different to my approach but I feel it will take me a little while to digest the difference. Thank you for taking the time. — MyDaftQuestions, Sep 15 '17 at 14:37
You're welcome! I've added a brief explanation of my approach. And here is the link to [**MDN's docs**](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce) about `reduce`. — ibrahim mahrir, Sep 15 '17 at 14:40

baao · Answer 2 · 2017-09-15T14:36:39.410

Below uses reduce to get the data grouped to a Map, then I convert the data to an object like you've shown above. You'll need a modern browser to run below snippet, or use a transpiler like babeljs to convert it to es5 syntax.

let currentData = [
    {'ticket':'CAP', 'child':'CT-1'},
    {'ticket':'CAP', 'child':'CT-2'},
    {'ticket':'CT-1', 'child':'CT-1-A'},
    {'ticket':'CT-1', 'child':'CT-1-B'}
];

let children = currentData.map(e => e.child);
currentData.sort((a,b) => children.indexOf(a.ticket));

let res = currentData.reduce((a,b) => {
    if (! children.includes(b.ticket)) {
        return a.set(b.ticket, (a.get(b.ticket) || [])
            .concat({ticket: b.child,
                children: currentData
                    .filter(el => el.ticket === b.child)
                    .map(el => ({ticket: el.child, children: []}))}))
    }
    return a;
}, new Map);

let r = {};

for (let [key,value] of res.entries()) {
    r.ticket = key;
    r.children = value;
}

console.log(r);

You might need to update your browser. Above uses some ES6 syntax and won't work with IE @MyDaftQuestions — baao, Sep 15 '17 at 14:34

score 1 · Answer 3 · answered Sep 15 '17 at 14:55

Solution using recursion, starting node can be changed.

var currentData = [{'ticket': 'cap','child': 'CT-1'}, {'ticket': 'cap','child': 'CT-2'}, {'ticket': 'CT-1','child': 'CT-1-A'}, {'ticket': 'CT-1','child': 'CT-1-B'}];

function convert(data, start){
  return {
    ticket: start,
    childs: data.filter(d => d.ticket == start)
                .reduce((curr, next) => curr.concat([next.child]), [])
                .map(c => convert(data, c))
  }
}

let result = convert(currentData, 'cap');

console.log(result);

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

score 1 · Answer 4 · answered Sep 15 '17 at 14:56

I would go with a simple for approach, like this:

var currentData = [
    {'ticket':'CAP', 'child':'CT-1'},
    {'ticket':'CAP', 'child':'CT-2'},
    {'ticket':'CT-1', 'child':'CT-1-A'},
    {'ticket':'CT-1', 'child':'CT-1-B'}
];
var leafs = {};
var roots = {};
var tickets = {};
for(var i=0; i<currentData.length; i++){
    var ticket = currentData[i].ticket;
    var child = currentData[i].child;
    if(!tickets[ticket]){
        tickets[ticket] = {ticket:ticket,children:[]};
        if(!leafs[ticket]){
            roots[ticket] = true;
        }
    }
    if(!tickets[child]){
        tickets[child] = {ticket:child,children:[]};
    }
    delete roots[child];
    leafs[child] = true;
    tickets[ticket].children.push(tickets[child]);
}
for(var ticket in roots){
    console.log(tickets[ticket]);
}

Koushik Chatterjee · Answer 5 · 2017-09-15T17:38:46.610

Well, if you are not familiar with reduce, map , forEach with callbacks to iterate, then here is a approach I came with, where the code is flat, storing object references in another map object and iterating exactly once the source array.

The code is much cleaner, if something is understandable add comments I will explain;

var currentData = [
    {'ticket':'CT-1', 'child':'CT-1-A'},
    {'ticket':'CT-1', 'child':'CT-1-B'},
    {'ticket':'CAP', 'child':'CT-1'},
    {'ticket':'CAP', 'child':'CT-2'}
];
function buildHierarchy(flatArr) {
    let root = {},
        nonRoot = {},
        tempMap = {};
    Object.setPrototypeOf(root, nonRoot);
    for (let idx = 0; idx < flatArr.length; idx++) {
        let currTicket = flatArr[idx];
        let tempTicket = tempMap[currTicket.ticket] || {ticket: currTicket.ticket, children: []};
        tempMap[currTicket.ticket] = tempTicket;
        if (currTicket.child) {
            let tempChild = tempMap[currTicket.child] || {ticket: currTicket.child, children: []};
            tempTicket.children.push(tempChild);
            tempMap[currTicket.child] = tempChild;
            delete root[tempChild.ticket];
            nonRoot[tempChild.ticket] = true;
        }
        root[tempTicket.ticket] = true;

    }
    return tempMap[Object.keys(root)[0]];
}

console.log(buildHierarchy(currentData));

I have changed the sequence of your source array in order to put the root object anywhere, and the code should work on that.

How to convert an array into a hierarchical array

5 Answers5