Build a Tree In JavaScript

Question

Hello guys I have a problem, I need to create a tree data structure, I'm not able to balance it, I tried some scripts over the internet and I couldn't find a solution, could someone help me?

I have an array of objects.

const data = [
      {
        id: 1111,
        code: '1',
        name: 'Item 1',
        parent_code: '',
        children: []
      },
      {
        id: 11110,
        code: '12',
        name: 'Item 12',
        parent_code: '1',
        children: []
      },
      {
        id: 99999,
        code: '3',
        name: 'Item 33',
        parent_code: '',
        children: []
      },
      {
        id: 99992,
        code: '114',
        name: 'Item 114',
        parent_code: '3',
        children: []
      },
      {
        id: 99993,
        code: '115',
        name: 'Item 115',
        parent_code: '114',
        children: []
      },
    ];

how do i need to leave

const expectedData = [
      {
        id: 1111,
        code: '1',
        name: 'Item 1',
        parent_code: '',
        children: [
          {
            id: 11110,
            code: '12',
            name: 'Item 12',
            parent_code: '1',
            children: []
          },
        ]
      },
      {
        id: 99999,
        code: '3',
        name: 'Item 33',
        parent_code: '',
        children: [
          {
            id: 99992,
            code: '114',
            name: 'Item 114',
            parent_code: '3',
            children: [
              {
                id: 99993,
                code: '115',
                name: 'Item 115',
                parent_code: '114',
                children: []
              },
            ]
          },
        ]
      },
    ]

I need to add the code and parent code, I tried something and got this result, but it is not what I would like

    let parents = [];

    data.forEach(d => {
      if(!d.parent_code) {
        d.children = data.filter(dt => dt.parent_code === dt.code);

        parents.push(d);
      }
    });

    console.log(parents);

The result was

const result = [
      {
        id: 1111,
        code: '1',
        name: 'Item 1',
        parent_code: '',
        children: [
          {
            id: 11110,
            code: '12',
            name: 'Item 12',
            parent_code: '1',
            children: []
          },
        ]
      },
      {
        id: 99999,
        code: '3',
        name: 'Item 33',
        parent_code: '',
        children: [
          {
            id: 99992,
            code: '114',
            name: 'Item 114',
            parent_code: '3',
            children: []
          },
        ]
      },
    ]

I couldn't get to the third level, look at parent_code 3

Answer 1

O(n) in-place solution

let r=[], h= data.reduce((a,c)=> (a[c.code]=c,a),{});
data.forEach((c,i,a,e=h[c.parent_code]) => (e ? e.children : r).push(c) );

const data = [
      {
        id: 1111,
        code: '1',
        name: 'Item 1',
        parent_code: '',
        children: []
      },
      {
        id: 11110,
        code: '12',
        name: 'Item 12',
        parent_code: '1',
        children: []
      },
      {
        id: 99999,
        code: '3',
        name: 'Item 33',
        parent_code: '',
        children: []
      },
      {
        id: 99992,
        code: '114',
        name: 'Item 114',
        parent_code: '3',
        children: []
      },
      {
        id: 99993,
        code: '115',
        name: 'Item 115',
        parent_code: '114',
        children: []
      },
    ];
    
let r=[], h= data.reduce((a,c)=> (a[c.code]=c,a),{});
data.forEach((c,i,a,e=h[c.parent_code]) => (e ? e.children : r).push(c) );

console.log(r);

Answer 2

You're pretty close:

data.forEach(d => {
  d.children = data.filter(dt => dt.parent_code === d.code);
  if(!d.parent_code) {
    parents.push(d);
  }
});

You want to find children for all elements, not just the roots. Also you mixed up d and dt a bit, parent and child would be more readable IMO.

---

Note that this is O(n²), an O(n) solution would be to create a Map from code to object, then iterate over the objects once, and push each object to the parent (which can be retrieved in O(1) from the Map). Then add the object itself to the Map. If the parent does not exist when the child gets iterated, add a new object as parent. Merge when the parent gets reached.

Answer 3

You could take anobject for the reference and build the tree in a single loop.

const
    data = [{ id: 1111, code: '1', name: 'Item 1', parent_code: '', children: [] }, { id: 11110, code: '12', name: 'Item 12', parent_code: '1', children: [] }, { id: 99999, code: '3', name: 'Item 33', parent_code: '', children: [] }, { id: 99992, code: '114', name: 'Item 114', parent_code: '3', children: [] }, { id: 99993, code: '115', name: 'Item 115', parent_code: '114', children: [] }],
    tree = function (data, root) {
        var t = {};
        data.forEach(o => {
            Object.assign(t[o.code] = t[o.code] || {}, o);
            t[o.parent_code] = t[o.parent_code] || {};
            t[o.parent_code].children = t[o.parent_code].children || [];
            t[o.parent_code].children.push(t[o.code]);
        });
        return t[root].children;
    }(data, '');

console.log(tree);

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