Building tree array of objects from flat array of objects [duplicate]

Question

I want to build a tree array from flat array:

Here is the flat array:

nodes = [
    {id: 1, pid: 0, name: "kpittu"},
    {id: 2, pid: 0, name: "news"},
    {id: 3, pid: 0, name: "menu"},
    {id: 4, pid: 3, name: "node"},
    {id: 5, pid: 4, name: "subnode"},
    {id: 6, pid: 1, name: "cace"}
];

NB: id = node id; pid = parent node id.

I want to transform it into this array:

nodes = [{
    id: 1,
    name: 'kpittu',
    childs: [{
        id: 6,
        name: 'cace'
    }]
}, {
    id: 2,
    name: 'news'
}, {
    id: 3,
    name: 'menu',
    childs: [{
        id: 4,
        name: 'node',
        childs: [{
            id: 5,
            name: 'subnode'
        }]
    }]
}];

I tried to use a recursive function to achieve the expected result, but I'm looking for a better approach. Thanks for your response.

Recommendation, if you don't figure out this yourself, you won't be able to learn or practice your recursive knowledge, instead fellow who answer this — asdf_enel_hak
– asdf_enel_hak, Commented Oct 20, 2017 at 10:52

Nina Scholz · Accepted Answer · 2017-10-20 11:01:29Z

5

You could use a hash table and take id and pid in every loop as connected nodes.

This proposal works with unsorted data as well.

var nodes = [{ id: 6, pid: 1, name: "cace" }, { id: 1, pid: 0, name: "kpittu" }, { id: 2, pid: 0, name: "news" }, { id: 3, pid: 0, name: "menu" }, { id: 4, pid: 3, name: "node" }, { id: 5, pid: 4, name: "subnode" }],
    tree = function (data, root) {
        var r = [], o = {};
        data.forEach(function (a) {
            if (o[a.id] && o[a.id].children) {
                a.children = o[a.id] && o[a.id].children;
            }
            o[a.id] = a;
            if (a.pid === root) {
                r.push(a);
            } else {
                o[a.pid] = o[a.pid] || {};
                o[a.pid].children = o[a.pid].children || [];
                o[a.pid].children.push(a);
            }
        });
        return r;
    }(nodes, 0);

console.log(tree);

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

answered Oct 20, 2017 at 11:01

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

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

3 Comments

SumNeuron Over a year ago

Can you update to handle a slight variant? In this case there is no parent id. Rather it is assumed that if the depth is lower or the same as the previous list element its parent is its predecessor

Nina Scholz Over a year ago

@SumNeuron, please add a new question with your try.

SumNeuron Over a year ago

see stackoverflow.com/questions/72292676/…

Yusuf · Accepted Answer · 2020-05-03 13:23:33Z

You can also use Map object, introduced in ES6.

let nodes = [
  { id: 1, pid: 0, name: "kpittu" },
  { id: 2, pid: 0, name: "news" },
  { id: 3, pid: 0, name: "menu" },
  { id: 4, pid: 3, name: "node" },
  { id: 5, pid: 4, name: "subnode" },
  { id: 6, pid: 1, name: "cace" }
];

function toTree(arr) {
  let arrMap = new Map(arr.map(item => [item.id, item]));
  let tree = [];

  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];

    if (item.pid) {
      let parentItem = arrMap.get(item.pid);

      if (parentItem) {
        let { children } = parentItem;

        if (children) {
          parentItem.children.push(item);
        } else {
          parentItem.children = [item];
        }
      }
    } else {
      tree.push(item);
    }
  }

  return tree;
}

let tree = toTree(nodes);

console.log(tree);

Ori Drori · Accepted Answer · 2017-10-20 11:09:24Z

Iterate with Array#reduce and a helper object:

var nodes = [
  {id: 1, pid: 0, name: "kpittu"},
  {id: 2, pid: 0, name: "news"},
  {id: 3, pid: 0, name: "menu"},
  {id: 4, pid: 3, name: "node"},
  {id: 5, pid: 4, name: "subnode"},
  {id: 6, pid: 1, name: "cace"}
];

const helper = nodes.reduce((h, o) => (h[o.id] = Object.assign({}, o), h), Object.create(null));

const tree = nodes.reduce((t, node) => {
  const current = helper[node.id];
  
  if(current.pid === 0) { // if it doesn't have a parent push to root
    t.push(current);
  } else {
    helper[node.pid].children || (helper[node.pid].children = []) // add the children array to the parent, if it doesn't exist
    helper[node.pid].children.push(current); // push the current item to the parent children array
  }
  
  return t;
}, []);

console.log(tree);

Collectives™ on Stack Overflow

Building tree array of objects from flat array of objects [duplicate]

3 Answers 3

3 Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Linked

Related