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
– ibrahim mahrir, Commented Sep 15, 2017 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
– MyDaftQuestions, Commented Sep 15, 2017 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
– doubleOrt, Commented Sep 15, 2017 at 14:10
@KoushikChatterjee, no, sadly it won't. I've updated my question — MyDaftQuestions
– MyDaftQuestions, Commented Sep 15, 2017 at 14:14

ibrahim mahrir · Accepted Answer · 2017-09-15 14:38:18Z

2

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.

edited Sep 15, 2017 at 14:38

answered Sep 15, 2017 at 14:27

ibrahim mahrir

31.8k5 gold badges50 silver badges78 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

MyDaftQuestions Over a year ago

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.

ibrahim mahrir Over a year ago

You're welcome! I've added a brief explanation of my approach. And here is the link to MDN's docs about reduce.

baao · Accepted Answer · 2017-09-15 14:36:39Z

1

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);

edited Sep 15, 2017 at 14:36

answered Sep 15, 2017 at 14:32

baao

73.6k18 gold badges152 silver badges209 bronze badges

2 Comments

baao Over a year ago

You might need to update your browser. Above uses some ES6 syntax and won't work with IE @MyDaftQuestions

baao Over a year ago

I activated babel, can you try it again? @MyDaftQuestions

Vanojx1 · Accepted Answer · 2017-09-15 14:55:10Z

1

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;}

answered Sep 15, 2017 at 14:55

Vanojx1

5,5842 gold badges25 silver badges37 bronze badges

Comments

Piyin · Accepted Answer · 2017-09-15 14:56:56Z

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 · Accepted Answer · 2017-09-15 17:38:46Z

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.

Collectives™ on Stack Overflow

How to convert an array into a hierarchical array

5 Answers 5

2 Comments

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related