Construct a tree from a flat list in javascript

Question

I have a flat list as shown below.

flatList = [
    {
        id: "39000000", 
        parent: null, 
        description: "Electric Systems", 
        name: "39000000"
    },
    {
        id: "39120000", 
        parent: "39000000", 
        description: "Electrical Equipment", 
        name: "39120000"
    },
    {
        id: "39121000", 
        parent: "39120000", 
        description: "Power Conditioning", 
        name: "39121000"
    },  
    {
        id: "39121011", 
        parent: "39121000", 
        description: "Uninterruptible Power Supply", 
        name: "39121011"
    }
];

Method to construct tree from flat list and store the tree in nestedList

nestedList = [];

getTree(flatList) {
    flatList.forEach(element => {
      if (!element.parent) {
        this.nestedList.push({ id: element.id, name: element.name, description: element.description, children: [] });
      } else {
        if (this.nestedList.findIndex(item => item.id === element.parent) === -1) {
          this.nestedList.push({
            id: element.id, name: element.name, description: element.description, children: [{ id: element.id, name: element.name, description: element.description, children: [] }]
          });
        } else {
          this.nestedList.find(item => item.id === element.parent).children.push(
            { id: element.id, name: element.name, description: element.description, children: [] }
          );
        }
      }
    });
  }

Output that I am getting looks like this.

nestedList = [
    {
        id: "39000000", 
        name: "39000000",  
        description: "Electric Systems", 
        children: [{
            id: "39120000", 
            name: "39120000", 
            description: "Electrical Equipment", 
            children: []}
        ]
    },
    {
        id: "39121000", 
        name: "39121000", 
        description: "Power Conditioning", 
        children: [{
                id: "39121000", 
                name: "39121000", 
                description: "Power Conditioning", 
                children: []
            },
            {
                id: "39121011", 
                name: "39121011", 
                description: "Uninterruptible Power Supply", 
                children: []
            }       
        ]
    }   
]

Desired output should be:

    nestedList = [
    {
      id: "39000000",
      name: "39000000",
      description: "Electric Systems",
      children: [{
        id: "39120000",
        name: "39120000",
        description: "Electrical Equipment",
        children: [{
          id: "39121000",
          name: "39121000",
          description: "Power Conditioning",
          children: [{
            id: "39121011",
            name: "39121011",
            description: "Uninterruptible Power Supply",
          }]
        }]
      }]
    }
  ]

Help would be appreciated.

You only look for the parents in the nested list. But the parent could be a child of one of the elements of the nested list. Use a Map, where every node is indexed by its ID. Then find the parent of each element in this map, and add the element to the children of the found parent. Then create an array containing all the nodes of the map that don't have any parent. This will be correct and more efficient. — JB Nizet, Jan 01 '19 at 07:52

Nurbol Alpysbayev · Accepted Answer · 2019-01-01T08:26:43.233

Here is the more modern code (explanation is under it):

    const src = [
        {
            id: "39000000", 
            parent: null, 
            description: "Electric Systems", 
            name: "39000000"
        },
        {
            id: "39120000", 
            parent: "39000000", 
            description: "Electrical Equipment", 
            name: "39120000"
        },
        {
            id: "39121000", 
            parent: "39120000", 
            description: "Power Conditioning", 
            name: "39121000"
        },  
        {
            id: "39121011", 
            parent: "39121000", 
            description: "Uninterruptible Power Supply", 
            name: "39121011"
        }
    ];

const findChildren = 
(parents, referenceArray) => 
  parents.map(({ id, parent, description, name }) =>
    ({ id, description, name, children: findChildren(referenceArray.filter(i =>
      i.parent === id), src) }))

console.log(findChildren(src.filter(i => i.parent === null), src))

The code finds root items (src.filter(i => i.parent === null)).
Those items are passed to findChildren function along with the reference array, which is the source array.
The findChildren function maps old object to a new format (removes parent, adds children props)...
... where children property is a result of another findChildren function call, but with arguments being next roots, i.e. children of current id.

P.S. this is also fully non-mutating solution, i.e. doesn't mutates the initial array.

Thanks for the sample code as well for the explanation. This works perfectly for me :) — Samvid, Jan 01 '19 at 14:52
@Samvid you are welcome! However on StackOverflow you say thanks by upvoting and accepting the answer! — Nurbol Alpysbayev, Jan 01 '19 at 17:01
yeah I know that. But, I am still building my reputation and hence it doesn't reflect publicly if I upvote! — Samvid, Jan 02 '19 at 09:05

Farhat Zaman · Answer 2 · 2019-01-01T15:42:45.507

try this function, hope so it will help you out.

flatList = [
    {
        id: "39000000", 
        parent: null, 
        description: "Electric Systems", 
        name: "39000000"
    },
    {
        id: "39120000", 
        parent: "39000000", 
        description: "Electrical Equipment", 
        name: "39120000"
    },
    {
        id: "39121000", 
        parent: "39120000", 
        description: "Power Conditioning", 
        name: "39121000"
    },  
    {
        id: "39121011", 
        parent: "39121000", 
        description: "Uninterruptible Power Supply", 
        name: "39121011"
    }
];
function getUnflatten(arry) {

    data = arry.reduce(function (r, a) {
        var index = 0, node;
        if (node && Object.keys(node).length) {
            node.children = node.children || [];
            node.children.push(a);
        } else {
            while (index < r.length) {
                    a.children = (a.children || []).concat(r.splice(index, 1));
            }
            r.push(a);
        }
        return r;
    }, []);

    return data;
}

let tree = getUnflatten(flatList)
console.log(tree);

Thanks! But this is exactly the inverse of the desired output as shown in the question. Can you please check? — Samvid, Jan 01 '19 at 12:47

Construct a tree from a flat list in javascript

2 Answers2