Removing items from a nested array with unknown depth

Question

I am trying to remove items from a nested array based on an array of correct matches.

Three requirements apply:

The depth of the array is unknown. Items can have nested children.
Only items without children should be removed
The items should be removed if they are not in the matching array

I have build a function to recursively get to the deepest level and filter the items based on the $match array.

This is what my code looks like so far:

import * as lodash from "https://cdn.skypack.dev/[email protected]";

let filterRecursively = (arr, match) => {
  // Recursively go to the deepest array we can find
  arr.forEach(el => {
      arr = el.children ? filterRecursively(el.children, match) : arr
  });

  // If we are at the deepest level we filter the items ...
  if (arr[0] && arr[0].children === undefined) {
    return _.filter(arr, (item) => {
        return match.includes(item.name)
    })
  } else { // ... if not we just return the array as-is
    return arr
  }
}

let arr = [
  {
    'name': 'John',
    'children': [
      {
        'name': 'John',
        'children': [
          { 'name': 'John' },
          { 'name': 'Jane' },
          { 'name': 'Joe' }
        ]
      }]
  }, {
    'name': 'Jeff',
    'children': [
      {
        'name': 'Joe',
        'children': [
          { 'name': 'Jill' },
          { 'name': 'Jeff' },
          { 'name': 'Joe' }
        ]
      }]
  }];

let match = ['John', 'Joe'];
let result = filterRecursively(arr, match);

console.log(result);

// Expected result:
 [
   {
     'name': 'John',
     'children': [
       {
         'name': 'John',
         'children': [
           { 'name': 'John' },
           { 'name': 'Joe' }
         ]
       }]
   }, {
     'name': 'Jeff',
     'children': [
       {
         'name': 'Joe',
         'children': [
           { 'name': 'Joe' }
         ]
       }]
   }];

// Current output
[
    {
        "name": "Joe"
    }
]

See the Codepen

In [{name: 'Jane', children: [{name: 'Jane'}]}] should the outermost Jane also be removed, since after processing the inner one, it will have no remaining children? Also, please see How do I create a runnable stack snippet? — Scott Sauyet
– Scott Sauyet, Commented Jun 3, 2022 at 12:34
Hi @ScottSauyet. No – only children at the deepest level should be removed. — Morten Najbjerg
– Morten Najbjerg, Commented Jun 3, 2022 at 12:38

user3297291 · Accepted Answer · 2022-06-03 13:08:22Z

Because the forEach basically "skips" layers without returning anything, you end up with just your first and deepest result.

I also think your function is a bit more complicated because it starts with an array, rather than a sort of ROOT node.

Here's an alternative that (I think) meets your requirements:

let childlessMatch = (node, match) => {
  // If it's at the deepest level, check against match
  if (node.children === undefined) {
    return match.includes(node.name) ? [node] : [];
  }
  
  // If not, calculate the next child layer first
  const newChildren = node.children.flatMap(c => childlessMatch(c, match));

  // With the children calculated, we can prune based on whether there
  // are any children left to show
  if (newChildren.length === 0) return [];
  
  return [{
    ...node,
    children: newChildren
  }]
}

In a runnable snippet:

let childlessMatch = (node, match) => {
  if (node.children === undefined) {
    return match.includes(node.name) ? [node] : [];
  }
  
  const newChildren = node.children.flatMap(c => childlessMatch(c, match));
  if (newChildren.length === 0) return [];
  
  return {
    ...node,
    children: newChildren
  }
}

let arr = [
  {
    'name': 'John',
    'children': [
      {
        'name': 'John',
        'children': [
          { 'name': 'John' },
          { 'name': 'Jane' },
          { 'name': 'Joe' }
        ]
      }]
  }, {
    'name': 'Jeff',
    'children': [
      {
        'name': 'Joe',
        'children': [
          { 'name': 'Jill' },
          { 'name': 'Jeff' },
          { 'name': 'Joe' }
        ]
      }]
  }];

let match = ['John', 'Joe'];
let result = childlessMatch({ children: arr }, match).children;

console.log(result);

Thanks I really appreciate your answer. While this is easier to interpret I ended up using the answer from @toptecshare as this worked with the proposed array structure. This might be helpful to others though :)

Scott Sauyet · Accepted Answer · 2022-06-03 13:14:15Z

I think it's better to separate out a generic node filtering technique that handles children appropriately from the code that checks the names. Here filterNodes accepts a predicate that says whether the node should be included (without worrying about children). It then does the child handling bit.

We write our main function by just passing a predicate that tests whether the name is on the allowed list.

Together, it looks like this:

const filterNodes = (pred) => (nodes) => 
  nodes .flatMap (
    (node, _, __, 
     kids = filterNodes (pred) (node .children || [])
    ) => pred (node) || node .children ?.length > 0 
      ? [{...node, ... (kids .length ? {children: kids} : {})}] 
      : []
  )

const removeUnmatchedNames = (names) =>
  filterNodes (({name}) => names .includes (name))


const arr = [{name: "John", children: [{name: "John", children: [{name: "John"}, {name: "Jane"}, {name: "Joe"}]}]}, {name: "Jeff", children: [{name: "Joe", children: [{name: "Jill"}, {name: "Jeff"}, {name: "Joe"}]}]}]

console .log (removeUnmatchedNames (['John', 'Joe']) (arr))

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

toptecshare · Accepted Answer · 2022-06-03 18:39:13Z

let filterRecursively = (arr, match) => {
  // Recursively go to the deepest array we can find
  return arr
    .map((el) =>
      el.children
        ? { ...el, children: filterRecursively(el.children, match) }
        : el
    )
    .filter((el) => el.children || match.includes(el.name));
};

I have updated filterRecursively.

      let filterRecursively = (arr, match) => {
      // Recursively go to the deepest array we can find
      return arr
        .map((el) =>
          el.children
            ? { ...el, children: filterRecursively(el.children, match) }
            : el
        )
        .filter((el) => el.children || match.includes(el.name));
    };
    
    let arr = [
      {
        name: "John",
        children: [
          {
            name: "John",
            children: [{ name: "John" }, { name: "Jane" }, { name: "Joe" }],
          },
        ],
      },
      {
        name: "Jeff",
        children: [
          {
            name: "Joe",
            children: [{ name: "Jill" }, { name: "Jeff" }, { name: "Joe" }],
          },
        ],
      },
    ];
    
    let match = ["John", "Joe"];
    let result = filterRecursively(arr, match);
    
    console.log(JSON.stringify(result));
    
    // Expected result:
    // [
    //   {
    //     'name': 'John',
    //     'children': [
    //       {
    //         'name': 'John',
    //         'children': [
    //           { 'name': 'John' },
    //           { 'name': 'Joe' }
    //         ]
    //       }]
    //   }, {
    //     'name': 'Jeff',
    //     'children': [
    //       {
    //         'name': 'Joe',
    //         'children': [
    //           { 'name': 'Joe' }
    //         ]
    //       }]
    //   }];

Simple solution – and it works really well without having to change the structure of my source array. Thanks a ton!

Collectives™ on Stack Overflow

Removing items from a nested array with unknown depth

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related