javascriptreducetree-structure

String-path to Tree (JavaScript)


I have an array of paths in string format like that:

[
  { _id: 'women/clothes/tops', count: 10 },
  { _id: 'women/clothes/suits', count: 5 },
  { _id: 'women/accessories', count: 2 },
  { _id: 'men/clothes', count: 1 },
]

I would like to group them into a tree structure like that:

[
  {
    _id: 'women',
    count: 17,
    children: [
      {
        _id: 'clothes',
        count: 15,
        children: [
          { _id: 'tops', count: 10 },
          { _id: 'suits', count: 5 }
        ]
      },
      {
        _id: 'accessories',
        count: 2
      }
    ]
  },
  {
    _id: 'men',
    count: 1,
    children: [
      {
        _id: 'clothes',
        count: 1
      }
    ]
  }
]

I would imagine a sort of recursive function calling a reduce method. But I can't figure how exactly.

EDIT :

I managed to get close with this solution. But I still get an empty object key, and i cannot manage to not have the children key when there are no children:


const getTree = (array) => {
  return array.reduce((a, b) => {
    const items = b._id.replace('\/', '').split('/')
    return construct(a, b.count, items)
  }, {})
}

const construct = (a, count, items) => {
  const key = items.shift()

  if(!a[key]) {
    a[key] = {
      _id: key,
      count: count,
      children: []
    }
    a[key].children = items.length > 0 ? construct(a[key].children, count, items) : null
  }
  else {
    a[key].count += count
    a[key].children = items.length > 0 ? construct(a[key].children, count, items) : null
  }
  return a
}

Solution

  • I created an object tree first and then converted that to your array of objects with children structure.

    Note: I used a _count property on each object in the intermediate structure so that when looping over the keys later (when creating the final structure), I could ignore both _id and _count easily, and loop over only the "real children" keys, which don't start with _.

    I did not look at your current attempt/solution before writing this, so mine looks quite different.

    const origData = [
      { _id: 'women/clothes/tops', count: 10 },
      { _id: 'women/clothes/suits', count: 5 },
      { _id: 'women/accessories', count: 2 },
      { _id: 'men/clothes', count: 1 },
    ];
    
    
    const newObj = {};
    for (let obj of origData) {
      //console.log(obj)
      const tempArr = obj._id.split('/');
      let tempHead = newObj; // pointer
      for (let idx in tempArr) {
        let head = tempArr[idx];
        if (!tempHead.hasOwnProperty(head)) {
          tempHead[head] = {};
        }
        tempHead = tempHead[head];
        tempHead._id = head;
        const currCount = tempHead._count || 0;
        tempHead._count = currCount + obj.count;
      }
      tempHead._count = obj.count;
    }
    
    console.log(newObj);
    const finalArr = [];
    let tempArrHead = finalArr; // pointer
    let tempObjHead = newObj; // pointer
    
    function recursiveStuff(currObj, currArr, copyObj) {
      let hasChildren = false;
      const keys = Object.keys(currObj).filter(a => !a.startsWith("_"));
      for (let key of keys) {
          hasChildren = true;
          const obj = {
            _id: currObj[key]._id,
            count: currObj[key]._count || 0,
            children: [],
          };
          currArr.push(obj);
          recursiveStuff(currObj[key], obj.children, obj)
      }
      if (hasChildren == false) {
        // console.log(copyObj);
        // there might be a more elegant way, but this works:
        delete copyObj.children;
      }
    }
    
    recursiveStuff(tempObjHead, tempArrHead)
    console.log(finalArr);
    .as-console-wrapper{
      max-height: 100% !important;
    }

    Intermediate Structure:

    {
      "women": {
        "_id": "women",
        "_count": 17,
        "clothes": {
          "_id": "clothes",
          "_count": 15,
          "tops": {
            "_id": "tops",
            "_count": 10
          },
          "suits": {
            "_id": "suits",
            "_count": 5
          }
        },
        "accessories": {
          "_id": "accessories",
          "_count": 2
        }
      },
      "men": {
        "_id": "men",
        "_count": 1,
        "clothes": {
          "_id": "clothes",
          "_count": 1
        }
      }
    }
    

    Final Structure:

    [
      {
        "_id": "women",
        "count": 17,
        "children": [
          {
            "_id": "clothes",
            "count": 15,
            "children": [
              {"_id": "tops", "count": 10},
              {"_id": "suits", "count": 5}
            ]
          },
          {"_id": "accessories", "count": 2}
        ]
      },
      {
        "_id": "men",
        "count": 1,
        "children": [
          {"_id": "clothes", "count": 1}
        ]
      }
    ]