Recursive filtering of array of objects without child nodes

Question

I want to filter an array of objects, recursively based on an input array that filters the values and filters out "empty nodes".

This is an example:

const nodes = [{
  value: 'World',
  children: [{
    value: 'Europe',
    children: [{
      value: 'BeNeLux',
      children: [{
        value: 'NL'
      }, {
        value: 'DE'
      }, {
        value: 'LU'
      }]
    }, {
      value: 'AL'
    }, {
      value: 'ZW'
    }, {
      value: 'UK' // lol
    }]
  }]
}]

In the array above, nodes have: value and optionally children.

I want a function, that I feed an input array that should filter the values + children of the nodes array as listed above so:

const valuesToBeRemoved = ['NL', 'DE', 'LU', 'ZW', 'UK']

The expected output should then be:

const expectedNodesOutput = [{
  value: 'World',
  children: [{
    value: 'Europe',
    children: [{
      value: 'AL'
    }]
  }]
}]

This is what I have tried but it is not working correctly because it's not correctly recursive, and it should filter out nodes that are empty (also curious on how other people come up with a solution that might be cleaner):

const filterNodes = (filter, node) => {
  if (node.children) {
    const children = node.children
      .map(child => filterNodes(filter, child))
      .filter(x => x)

    if (children.length) {
      return {
        ...node,
        children
      }
    }
  } else {
    if (!filter.includes(node.value)) {
      return node
    }
  }
}

const getFilteredNodes = (filter, nodes) => {
  return filterNodes(filter, { children: nodes })?.children || []
}

Here is a codepen: https://codepen.io/anon/pen/KOXBLe

@alfasin not sure about that, the code isn't working as intended — user11523568
– user11523568, Commented Aug 3, 2019 at 18:41
@alfasin no it's not. Code Review requires that the existing code works as intended. It is explicitly stated in the question that the existing code does not. — Patrick Roberts
– Patrick Roberts, Commented Aug 3, 2019 at 18:42
Then clarify your question, right now you ask "if there would be a cleaner / more efficient way" which implies this code works. — Nir Alfasi
– Nir Alfasi, Commented Aug 3, 2019 at 18:42
I didn't downvote, but I honestly don't think this question should be upvoted until it gets cleaned up... — Nir Alfasi
– Nir Alfasi, Commented Aug 3, 2019 at 18:45
@dfhwze it could have prevented half of the questions on this website LoL :) — Nir Alfasi
– Nir Alfasi, Commented Aug 3, 2019 at 18:48

Nina Scholz · Accepted Answer · 2019-08-03 18:59:45Z

filter does not respect nested properties and otjherwise, you need to mutate the given data structure.

Instead, you could reduce the node structure by looking at the children and if an not empty array is returned, take the actual value as well.

function filter(array, remove) {
    return array.reduce((r, { value, children }) => {
        if (remove.includes(value)) return r;
        if (!children) {
            r.push({ value });
            return r;
        }
        children = filter(children, remove);
        if (children.length) r.push({ value, children });
        return r;
    }, []);
}

var nodes = [{ value: 'World', children: [{ value: 'Europe', children: [{ value: 'BeNeLux', children: [{ value: 'NL' }, { value: 'DE' }, { value: 'LU' }] }, { value: 'AL' }, { value: 'ZW' }, { value: 'UK' }] }] }],
    remove = ['NL', 'DE', 'LU', 'ZW', 'UK'],
    result = filter(nodes, remove);

console.log(result);

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

Patrick Roberts · Accepted Answer · 2019-08-03 19:56:32Z

Here's an immutable way to remove values and prune the empty arrays from the recursive structure. They need to be performed separately in order for pruning to respect the modifications caused by removed values:

function remove (nodes, values) {
  return nodes.map(
    ({ value, children }) => children
      ? { value, children: remove(children, values) }
      : { value }
  ).filter(
    ({ value }) => !values.includes(value)
  );
}

function prune (nodes) {
  return nodes.map(
    ({ value, children }) => children
      ? { value, children: prune(children) }
      : { value }
  ).filter(
    ({ children }) => !children || children.length > 0
  );
}

const nodes = [{
  value: 'World',
  children: [{
    value: 'Europe',
    children: [{
      value: 'BeNeLux',
      children: [{
        value: 'NL'
      }, {
        value: 'DE'
      }, {
        value: 'LU'
      }]
    }, {
      value: 'AL'
    }, {
      value: 'ZW'
    }, {
      value: 'UK'
    }]
  }]
}];

const valuesToBeRemoved = ['NL', 'DE', 'LU', 'ZW', 'UK'];

console.log(prune(remove(nodes, valuesToBeRemoved)));

You can even make the code more DRY by using a higher order function to define remove() and prune():

const recurseBy = key => filter => function callback (nodes, ...args) {
  return nodes.map(
    ({ [key]: nodes, ...rest }) => nodes
      ? { ...rest, [key]: callback(nodes, ...args) }
      : { ...rest }
  ).filter(
    item => filter(item, ...args)
  );
};

const filterBy = recurseBy('children');
const remove = filterBy(({ value }, values) => !values.includes(value));
const prune = filterBy(({ children }) => !children || children.length > 0);

const nodes = [{
  value: 'World',
  children: [{
    value: 'Europe',
    children: [{
      value: 'BeNeLux',
      children: [{
        value: 'NL'
      }, {
        value: 'DE'
      }, {
        value: 'LU'
      }]
    }, {
      value: 'AL'
    }, {
      value: 'ZW'
    }, {
      value: 'UK'
    }]
  }]
}];

const valuesToBeRemoved = ['NL', 'DE', 'LU', 'ZW', 'UK'];

console.log(prune(remove(nodes, valuesToBeRemoved)));

I noticed in the question you used optional chaining syntax. If your project allows ESnext (aka TC39 proposals), you can use the pipeline operator and partial application syntax to clean up the calls.

console.log(prune(remove(nodes, valuesToBeRemoved)));

is equivalent to

nodes
  |> remove(?, valuesToBeRemoved)
  |> prune(?)
  |> console.log(?)

Collectives™ on Stack Overflow

Recursive filtering of array of objects without child nodes

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related