Javascript - Get all the objects from an array that is direct/nested children of another object

kazinurhossaintipu
October 18, 2023
250 views
3 votes
4 Answers

So I have a javascript array that looks like this (simplified).
Here beauty (id:1) and health (id:2) is root categories as they have a null value of parentCategoryId.
hair care (id:3), hair oil (id:4) and kumarika hair oil (id:5) falls into the beauty category(id:1) as they have parentCategoryId value which directly or indirectly falls into beauty category(see below for explaination).But supplements (id:6) falls into the health category (id:2).
How do I get all the categories that (directly or nested) falls into the beauty category (id:1).
key parentCategoryId is the identifier of which category directly falls into which category.
so here

id:3 has parentCategoryId:1 that means id:3 is direct children of id:1.So falls into beauty category.

id:4 has parentCategoryId:3 that means id:4 is direct children of id:3 which is direct children of id:1.so falls into beauty category.

id:5 has parentCategoryId:4 that means id:5 is direct children of id:4 which is direct children of id:3 which is direct children of id:1 and falls into beauty category.

const categories = [
    {id:1,name:'beauty',parentCategoryId:null},
    {id:2, name:'health', parentCategoryId:null},
    {id:3, name:'hair care', parentCategoryId:1},
    {id:4, name:'hair oil', parentCategoryId:3},
    {id:5, name:'kumarika hair oil', parentCategoryId:4},
    {id:6, name:'supplements', parentCategoryId:2}
]

I have tried recursive function but couldn’t find the appropriate output.Say for example I am calling this recursive function with the object that has id:1.

let newCategoriesArray =[]

 const getAllChildCategories = (category) => {
    let childCategories = categories.filter(
      (cat) => cat.parentCategory == category.id
    );
   
    newCategoriesArray.push(...childCategories);
    
    if (childCategories.length > 0) {
      childCategories.map((cat) => {
        getAllChildCategories(cat);
      });
    }
  };

My expected output should be an array of categories that is direct or nested children of beauty (id:1 ).
So the new array should look like this.please take into consideration there may exist more nested categorie.

const newCategoriesArray  = [
    {id:3, name:'hair care', parentCategoryId:1},
    {id:4, name:'hair oil', parentCategoryId:3},
    {id:5, name:'kumarika hair oil', parentCategoryId:4},
]

Answers

filter() was a good direction, just it can’t access its own results on the go, and that’s why the 4–5 pair becomes hard. reduce() gives access to the result all the time, I’d suggest using that:

const categories = [
  {id:1,name:'beauty',parentCategoryId:null},
  {id:2, name:'health', parentCategoryId:null},
  {id:3, name:'hair care', parentCategoryId:1},
  {id:4, name:'hair oil', parentCategoryId:3},
  {id:5, name:'kumarika hair oil', parentCategoryId:4},
  {id:6, name:'supplements', parentCategoryId:2}
];

function filterThing(id) {
  return categories.reduce((result, item) => {
    if (item.parentCategoryId === id
        || result.find(fitem => fitem.id === item.parentCategoryId)) // (*)
      result.push(item);
    return result;
  }, []);
}

console.log(filterThing(1));
console.log("---");
console.log(filterThing(2));

The (*) part is what filter() can’t do directly.
This approach builds on that sub-categories always appear after their parent, so for example "kumarika hair oil" will never come before "hair oil" (and "beauty"). If that’s not true, it won’t work.

After seeing the comment here is a variant that does not rely on the order of categories-subcategories (input array has been rearranged). It preprocesses the original data into a parentCategory-indexed array of arrays, and then takes the result from that one with a very minimal recursive step, taking the preprocessed item directly (the ...prep[id] part) and then checking if those items have descendants (the part with the flatMap() call):

const categories = [
  {id:4, name:'hair oil', parentCategoryId:3},
  {id:1, name:'beauty',parentCategoryId:null},
  {id:2, name:'health', parentCategoryId:null},
  {id:3, name:'hair care', parentCategoryId:1},
  {id:5, name:'kumarika hair oil', parentCategoryId:4},
  {id:6, name:'supplements', parentCategoryId:2}
];

const prep = categories.reduce((result, item) => {
  const pid = item.parentCategoryId;
  if (pid !== null) {
    if (!result[pid])
      result[pid] = [];
    result[pid].push(item);
  }
  return result;
}, []);

function filterThing(id) {
  if (!prep[id]) return [];
  return [...prep[id], ...prep[id].flatMap(x => filterThing(x.id))];
}

console.log(filterThing(1));
console.log("---");
console.log(filterThing(2));

I think something similar may have appeared in one of the deleted answers, but it’s not visible now.

You have some interesting options already, provided categories isn’t a very long list (like thousands of entries). (They do lots of looping through the list.)

If there are a lot of categories in the list (at least thousands), but the hierarchies aren’t hundreds deep, I’d probably just loop through categories once, checking the ancestry of each target category as I went.

I’d start by keeping a map of categories by their ID (just after the categories array, unless that’s dynamic; if it’s dynamic, create the map on the fly):

const categoriesById = new Map(
    categories.map((category) => [category.id, category])
);

Then get the target category ID (since you seem to be starting with a category object) and an array for the results:

const targetId = category.id;
const results = [];

Then loop through the categories:

for (const cat of categories) {

In the loop, we’ll go through cat‘s ancestors (if any) seeing if any of them matches the target:

    // Start with this category in `c`...
    let c = cat;
    // While `c` exists and has a parent...
    while (c && c.parentCategoryId) {
        // Get its parent
        c = c.parentCategoryId && categoriesById.get(c.parentCategoryId);
        // Does the parent match?
        if (c.id === targetId) {
            // Found it
            results.push(cat);
            break;
        }
        // The loop will continue searching ancestry of `cat` via `c`
    }

and that’s it!

Working example (rather shorter without the explanatory comments):

const categories = [ { id: 1, name: "beauty", parentCategoryId: null }, { id: 2, name: "health", parentCategoryId: null }, { id: 3, name: "hair care", parentCategoryId: 1 }, { id: 4, name: "hair oil", parentCategoryId: 3 }, { id: 5, name: "kumarika hair oil", parentCategoryId: 4 }, { id: 6, name: "supplements", parentCategoryId: 2 }, ];
const categoriesById = new Map( categories.map((category) => [category.id, category]));

const getAllChildCategories = (category) => {
    const targetId = category.id;
    const results = [];
    for (const cat of categories) {
        let c = cat;
        while (c && c.parentCategoryId) {
            c = c.parentCategoryId && categoriesById.get(c.parentCategoryId);
            if (c.id === targetId) {
                results.push(cat);
                break;
            }
        }
    }
    return results;
};

console.log(getAllChildCategories(categories[0]));

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

A quite popular solution would be to build a parent id map with children for particular parent id and traverse this map (this is good when the order of the items is random), otherwise tevemadar’s solution is faster (but not very safe as T.J. Crowder mentioned).

const categories = [
  {id:1,name:'beauty',parentCategoryId:null},
  {id:2, name:'health', parentCategoryId:null},
  {id:3, name:'hair care', parentCategoryId:1},
  {id:4, name:'hair oil', parentCategoryId:3},
  {id:5, name:'kumarika hair oil', parentCategoryId:4},
  {id:6, name:'supplements', parentCategoryId:2}
];

const parentMap = {};
categories.forEach(c => (parentMap[c.parentCategoryId] ??= []).push(c));

function findChildren(id, children = []) {
  const found = parentMap[id];
  if(found){
    children.push(...found);
    found.forEach(c => findChildren(c.id, children));
  }
  return children;
}

console.log(findChildren(1));

` Chrome/118
------------------------------------------------------------
tevemadar       1.00x  |  x10000000  589  594  615  633  638
Alexander       7.61x  |   x1000000  448  467  468  482  486
T.J. Crowder   11.24x  |   x1000000  662  671  681  686  692
------------------------------------------------------------
https://github.com/silentmantra/benchmark `

` Firefox/118
----------------------------------------------------------
tevemadar      1.00x  |  x1000000  294  309  323  329  338
Alexander      2.86x  |  x1000000  840  851  854  854  855
T.J. Crowder   5.03x  |   x100000  148  149  151  151  154
----------------------------------------------------------
https://github.com/silentmantra/benchmark `

const categories = [
      {id:1,name:'beauty',parentCategoryId:null},
      {id:2, name:'health', parentCategoryId:null},
      {id:3, name:'hair care', parentCategoryId:1},
      {id:4, name:'hair oil', parentCategoryId:3},
      {id:5, name:'kumarika hair oil', parentCategoryId:4},
      {id:6, name:'supplements', parentCategoryId:2},
      {id:11,name:'beauty',parentCategoryId:null},
      {id:12, name:'health', parentCategoryId:null},
      {id:13, name:'hair care', parentCategoryId:11},
      {id:14, name:'hair oil', parentCategoryId:13},
      {id:15, name:'kumarika hair oil', parentCategoryId:14},
      {id:16, name:'supplements', parentCategoryId:12},
      {id:21,name:'beauty',parentCategoryId:null},
      {id:22, name:'health', parentCategoryId:null},
      {id:23, name:'hair care', parentCategoryId:21},
      {id:24, name:'hair oil', parentCategoryId:23},
      {id:25, name:'kumarika hair oil', parentCategoryId:24},
      {id:26, name:'supplements', parentCategoryId:22},
];

// @benchmark T.J. Crowder

const category = categories.find(({id}) => id === 21);

// @run
const categoriesById = new Map( categories.map((category) => [category.id, category]));

const getAllChildCategories = (category) => {
    const targetId = category.id;
    const results = [];
    for (const cat of categories) {
        let c = cat;
        while (c && c.parentCategoryId) {
            c = c.parentCategoryId && categoriesById.get(c.parentCategoryId);
            if (c.id === targetId) {
                results.push(cat);
                break;
            }
        }
    }
    return results;
};

getAllChildCategories(category);

// @benchmark tevemadar

function filterThing(id) {
  return categories.reduce((result, item) => {
    if (item.parentCategoryId === id
        || result.find(fitem => fitem.id === item.parentCategoryId)) // (*)
      result.push(item);
    return result;
  }, []);
}

filterThing(21);

// @benchmark Alexander
const parentMap = {};
categories.forEach(c => (parentMap[c.parentCategoryId] ??= []).push(c));

function findChildren(id, children = []) {
  const found = parentMap[id];
  if(found){
    children.push(...found);
    found.forEach(c => findChildren(c.id, children));
  }
  return children;
}

filterThing(21);

/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));

This solution uses stack data structure to achieve this. I would consider this an optimal solution. The time complexity is O(n). I have left comments every step of the way to explain how I came up with it.

const categories = [{
    id: 1,
    name: 'beauty',
    parentCategoryId: null
  },
  {
    id: 2,
    name: 'health',
    parentCategoryId: null
  },
  {
    id: 3,
    name: 'hair care',
    parentCategoryId: 1
  },
  {
    id: 4,
    name: 'hair oil',
    parentCategoryId: 3
  },
  {
    id: 5,
    name: 'kumarika hair oil',
    parentCategoryId: 4
  },
  {
    id: 6,
    name: 'supplements',
    parentCategoryId: 2
  }
];

/*
    Define categories map, to hold the relationship between parent id and sub children
*/
const categoriesMap = new Map();

/*
    Transform categoriesMap into map of { parentId: [childCategories] }, to avoid high time complexity. Ideally, this is done once
*/
for (const category of categories) {
    const mapItem = categoriesMap.get(category.id);
    const parentMapItem = categoriesMap.get(category.parentCategoryId);
  
    if (!mapItem) {
      categoriesMap.set(category.id, []);
    }

    // Create Parent Item on map
    if (!parentMapItem) {
      categoriesMap.set(category.parentCategoryId, [category]);
    } else {
      parentMapItem.push(category);
    }
}

/* Function to get all child categories*/
function getAllChildCategories(category) {
    // Data structure to hold categories to check
  const categoriesStack = [category];
  
  // This is to store already checked categories, so as not to check them again.
  const categoriesSet = new Set();
  const childCategories = [];

    // Loop through stack and handle each category
  while (categoriesStack.length > 0) {
    const currentCategory = categoriesStack.shift();
    const subCategories = categoriesMap.get(currentCategory.id);
    
    // Check that we haven't done a check for this particular item before
    if (!categoriesSet.has(currentCategory.id)) {
        // Add items to stack
        categoriesStack.unshift(...subCategories);
        // Add items to child array
        childCategories.push(...subCategories);
    }
    
    // Make sure to indicate that currentCategory has been traversed, and shouldn't be traversed subsequently
    categoriesSet.add(currentCategory.id);
  }

  return childCategories;
}

console.log(getAllChildCategories(categories[0]));
/*
    Should log out
  [{
    id: 3,
    name: "hair care",
    parentCategoryId: 1
  }, {
    id: 4,
    name: "hair oil",
    parentCategoryId: 3
  }, {
    id: 5,
    name: "kumarika hair oil",
    parentCategoryId: 4
  }]
*/

Please signup or login to give your own answer.

Click here to cancel reply.

Javascript – Get all the objects from an array that is direct/nested children of another object

Answers