Recursively filter array of objects

Question

Hitting a wall with this one, thought I would post it here in case some kind soul has come across a similar one. I have some data that looks something like this:

const input = [
  {
    value: 'Miss1',
    children: [
      { value: 'Miss2' },
      { value: 'Hit1', children: [ { value: 'Miss3' } ] }
    ]
  },
  {
    value: 'Miss4',
    children: [
      { value: 'Miss5' },
      { value: 'Miss6', children: [ { value: 'Hit2' } ] }
    ]
  },
  {
    value: 'Miss7',
    children: [
      { value: 'Miss8' },
      { value: 'Miss9', children: [ { value: 'Miss10' } ] }
    ]
  },
  {
    value: 'Hit3',
    children: [
      { value: 'Miss11' },
      { value: 'Miss12', children: [ { value: 'Miss13' } ] }
    ]
  },
  {
    value: 'Miss14',
    children: [
      { value: 'Hit4' },
      { value: 'Miss15', children: [ { value: 'Miss16' } ] }
    ]
  },
];

I don't know at run time how deep the hierarchy will be, i.e. how many levels of objects will have a children array. I have simplified the example somewhat, I will actually need to match the value properties against an array of search terms. Let's for the moment assume that I am matching where value.includes('Hit').

I need a function that returns a new array, such that:

Every non-matching object with no children, or no matches in children hierarchy, should not exist in output object
Every object with a descendant that contains a matching object, should remain
All descendants of matching objects should remain

I am considering a 'matching object' to be one with a value property that contains the string Hit in this case, and vice versa.

The output should look something like the following:

const expected = [
  {
    value: 'Miss1',
    children: [
      { value: 'Hit1', children: [ { value: 'Miss3' } ] }
    ]
  },
  {
    value: 'Miss4',
    children: [
      { value: 'Miss6', children: [ { value: 'Hit2' } ] }
    ]
  },
  {
    value: 'Hit3',
    children: [
      { value: 'Miss11' },
      { value: 'Miss12', children: [ { value: 'Miss13' } ] }
    ]
  },
  {
    value: 'Miss14',
    children: [
      { value: 'Hit4' },
    ]
  }
];

Many thanks to anyone who took the time to read this far, will post my solution if I get there first.

So it seems you're saying that ultimately, only the objects in the outermost array will be included in the result, since if anything nested inside matches, its entire structure is retained. In that case, seems like you just need `input.filter(function(o) {...})`, where the function makes a recursive call that returns `true` when/if a match is ultimately found. — , Jun 30 '16 at 20:02
@squint Not quite. Notice how `Miss2` was removed from the children of `Miss1` — 4castle, Jun 30 '16 at 20:05
@4castle: Good point, but then I wonder why others are not removed. What am I missing? — , Jun 30 '16 at 20:06
@squint Read their criteria very carefully. The output is exactly as they said. — 4castle, Jun 30 '16 at 20:07
Have you looked into the [Lodash](https://lodash.com) javascript library which contains lots of methods to operate on lists. (like linq if you are familiar with dotnet) It is a cleaner version of [Underscore](http://underscorejs.org). — LosManos, Jun 30 '16 at 20:23

score 68 · Accepted Answer · edited Jun 30 '16 at 21:12

68

Using .filter() and making a recursive call as I described in the comment above is basically what you need. You just need to update each .children property with the result of the recursive call before returning.

The return value is just the .length of the resulting .children collection, so if there's at least one, the object is kept.

var res = input.filter(function f(o) {
  if (o.value.includes("Hit")) return true

  if (o.children) {
    return (o.children = o.children.filter(f)).length
  }
})

const input = [
  {
    value: 'Miss1',
    children: [
      { value: 'Miss2' },
      { value: 'Hit1', children: [ { value: 'Miss3' } ] }
    ]
  },
  {
    value: 'Miss4',
    children: [
      { value: 'Miss5' },
      { value: 'Miss6', children: [ { value: 'Hit2' } ] }
    ]
  },
  {
    value: 'Miss7',
    children: [
      { value: 'Miss8' },
      { value: 'Miss9', children: [ { value: 'Miss10' } ] }
    ]
  },
  {
    value: 'Hit3',
    children: [
      { value: 'Miss11' },
      { value: 'Miss12', children: [ { value: 'Miss13' } ] }
    ]
  },
  {
    value: 'Miss14',
    children: [
      { value: 'Hit4' },
      { value: 'Miss15', children: [ { value: 'Miss16' } ] }
    ]
  },
];

var res = input.filter(function f(o) {
  if (o.value.includes("Hit")) return true

  if (o.children) {
    return (o.children = o.children.filter(f)).length
  }
})
console.log(JSON.stringify(res, null, 2))

Note that .includes() on a String is ES7, so may need to be patched for legacy browsers. You can use the traditional .indexOf("Hit") != -1 in its place.

To not mutate the original, create a map function that copies an object and use that before the filter.

function copy(o) {
  return Object.assign({}, o)
}

var res = input.map(copy).filter(function f(o) {
  if (o.value.includes("Hit")) return true

  if (o.children) {
    return (o.children = o.children.map(copy).filter(f)).length
  }
})

To really squeeze the code down, you could do this:

var res = input.filter(function f(o) {
  return o.value.includes("Hit") ||
         o.children && (o.children = o.children.filter(f)).length
})

Though it gets a little hard to read.

edited Jun 30 '16 at 21:12

4castle

32,613
11
69
106

answered Jun 30 '16 at 20:22

3

It alters the contents of the original `input`. You might first want to make a copy with `JSON.parse(JSON.stringify(input))`. Also, I get the feeling that this is server-side JS. – 4castle Jun 30 '16 at 20:27
Simplest would be to clone the whole structure from the start. If each object truly only has 2 properties, then first doing a `.map()` on each one before the `.filter()` should be simple enough. – Jun 30 '16 at 20:31
@squint Is requirement to include `children` array in result if `children` array does not contain `"Hit"` where `value` of preceding object `value` contains `"Hit"`? For example, item at index `3` of filtered array? – guest271314 Jun 30 '16 at 20:41
Yep, if the parent has a match, then all children are included – Nathan Power Jun 30 '16 at 20:43
Gotta give this one the accepted answer for completeness, and because I am going to use it, although others look good too. – Nathan Power Jun 30 '16 at 20:44
@guest271314 The output exactly matches the expected output. – 4castle Jun 30 '16 at 20:44
@4castle `{ value: 'Miss14', children: [ { value: 'Hit4' }, { value: 'Miss15', children: [ { value: 'Miss16' } ] } ] }` should be excluded from output? See _"Every object with a descendant that contains a matching object, should remain"_ – guest271314 Jun 30 '16 at 20:46
@guest271314 Being a hit doesn't protect siblings, only parents and children. So the second child will be removed. – 4castle Jun 30 '16 at 20:48
1

@guest271314: I think you may be thinking of it as I originally was, where even if something has a descendant that has a "hit", *all* its descendants would be kept. That would actually be pretty easy too, but from the description and the output shown, the only misses that are kept are either a descendant of a "hit" or an ancestor of one. – Jun 30 '16 at 20:51
This solution works for two-level deep nested arrays. How do we make it work for n-level deep nested arrays? – Thracian Aug 29 '19 at 20:54
1

can you please explain why `length` is required in `return (o.children = o.children.filter(f)).length` ? – Sapnesh Naik Mar 05 '20 at 09:30
1

@Sapnesh Naik If the length of children which are a "hit" is 0, this 0 will return as falsy, and thus the filter will trim it. Conversely, if a "hit" is found, the length will be larger than 0, so it will return as true, and filter will include/return it. – cdehaan Oct 22 '21 at 09:43

score 15 · Answer 2 · answered Jun 30 '16 at 20:20

Here's a function that'll do what you're looking for. Essentially it will test every item in arr for a match, then recursively call filter on its children. Also Object.assign is used so that the underlying object isn't changed.

function filter(arr, term) {
    var matches = [];
    if (!Array.isArray(arr)) return matches;

    arr.forEach(function(i) {
        if (i.value.includes(term)) {
            matches.push(i);
        } else {
            let childResults = filter(i.children, term);
            if (childResults.length)
                matches.push(Object.assign({}, i, { children: childResults }));
        }
    })

    return matches;
}

Thanks, this approach actually made clearer to me where I was going wrong — Nathan Power, Jun 30 '16 at 20:45
I think it's a but confusing to call it 'filter', as 'filter' is already an array method in Javascript. We could call it 'search' — Raphael Pinel, Jun 01 '21 at 05:52

score 2 · Answer 3 · answered Jun 30 '16 at 20:34

I think it will be a recursive solution. Here is one that I tried.

function find(obj, key) {
  if (obj.value && obj.value.indexOf(key) > -1){
    return true;
  }
  if (obj.children && obj.children.length > 0){
    return obj.children.reduce(function(obj1, obj2){
      return find(obj1, key) || find(obj2, key);
    }, {}); 
  } 
  return false;
}

var output = input.filter(function(obj){
     return find(obj, 'Hit');
 });
console.log('Result', output);

score 1 · Answer 4 · answered Feb 17 '20 at 09:49

const input = [
  {
    value: 'Miss1',
    children: [
      { value: 'Miss1' },
      { value: 'Hit1', children: [ { value: 'Miss3' } ] }
    ]
  },
  {
    value: 'Miss4',
    children: [
      { value: 'Miss5' },
      { value: 'Miss6', children: [ { value: 'Hit2' } ] }
    ]
  },
  {
    value: 'Miss7',
    children: [
      { value: 'Miss8' },
      { value: 'Miss9', children: [ { value: 'Miss10' } ] }
    ]
  },
  {
    value: 'Hit3',
    children: [
      { value: 'Miss11' },
      { value: 'Miss12', children: [ { value: 'Miss13' } ] }
    ]
  },
  {
    value: 'Miss14asds',
    children: [
      { value: 'Hit4sdas' },
      { value: 'Miss15', children: [ { value: 'Miss16' } ] }
    ]
  },
];

function filter(arr, term) {
    var matches = [];
    
    if (!Array.isArray(arr)) return matches;

    arr.forEach(function(i) {
     
        if (i.value === term) {
    
         const filterData =  (i.children && Array.isArray(i.children))? i.children.filter(values => values.value ===term):[];
         console.log(filterData)
         i.children =filterData;
            matches.push(i);
          
        } else {
       // console.log(i.children)
            let childResults = filter(i.children, term);
            if (childResults.length)
     matches.push(Object.assign({}, i, { children: childResults }));
        }
    })

    return matches;
}


const filterData= filter(input,'Miss1');
console.log(filterData)

Below code for filter the parent and child array data using recursive function

const input = [
  {
    value: 'Miss1',
    children: [
      { value: 'Miss2' },
      { value: 'Hit1', children: [ { value: 'Miss3' } ] }
    ]
  },
  {
    value: 'Miss4',
    children: [
      { value: 'Miss5' },
      { value: 'Miss6', children: [ { value: 'Hit2' } ] }
    ]
  },
  {
    value: 'Miss7',
    children: [
      { value: 'Miss8' },
      { value: 'Miss9', children: [ { value: 'Miss10' } ] }
    ]
  },
  {
    value: 'Hit3',
    children: [
      { value: 'Miss11' },
      { value: 'Miss12', children: [ { value: 'Miss13' } ] }
    ]
  },
  {
    value: 'Miss14',
    children: [
      { value: 'Hit4' },
      { value: 'Miss15', children: [ { value: 'Miss16' } ] }
    ]
  },
];

var res = input.filter(function f(o) {
  if (o.value.includes("Hit")) return true

  if (o.children) {
    return (o.children = o.children.filter(f)).length
  }
})
console.log(JSON.stringify(res, null, 2))

Malik Bagwala · Answer 5 · 2020-10-31T04:42:15.900

1

Here is a good solution which utilizes the array reduce function which results in more readable code then the other solutions. Also it is more readable in my opinion. We are calling the filter function recursively to filter an array along with its children

const input = [
  {
    value: "Miss1",
    children: [
      { value: "Miss2" },
      { value: "Hit1", children: [{ value: "Miss3" }] },
    ],
  },
  {
    value: "Miss4",
    children: [
      { value: "Miss5" },
      { value: "Miss6", children: [{ value: "Hit2" }] },
    ],
  },
  {
    value: "Miss7",
    children: [
      { value: "Miss8" },
      { value: "Miss9", children: [{ value: "Miss10" }] },
    ],
  },
  {
    value: "Hit3",
    children: [
      { value: "Miss11" },
      { value: "Miss12", children: [{ value: "Miss13" }] },
    ],
  },
  {
    value: "Miss14",
    children: [
      { value: "Hit4" },
      { value: "Miss15", children: [{ value: "Miss16" }] },
    ],
  },
];

function recursiveFilter(arr) {
  return arr.reduce(function filter(prev, item) {
    if (item.value.includes("Hit")) {
      if (item.children && item.children.length > 0) {
        return prev.concat({
          ...item,
          children: item.children.reduce(filter, []),
        });
      } else {
        return item;
      }
    }
    return prev;
  }, []);
}

console.log(recursiveFilter(input));

edited Oct 31 '20 at 04:42

answered Oct 29 '20 at 09:06

Malik Bagwala

2,695
7
23
38

Please submit existing solutions to other problems only if they actually solve the problem at hand; the question has nothing to do with `route`s or `isAuthorized.`. If there are analogies to make, please make them. Also, your brief into is not enough to stop this from being a code-only solution; don't post those. Finally, when resurrecting an old question, please make sure you have something new to add. – Scott Sauyet Oct 29 '20 at 13:07
@ScottSauyet sorry for the lack of context, I added the necessary changes and I feel this particular solution is more readable and reasonable compared to other solutions. – Malik Bagwala Oct 30 '20 at 03:34
@mailk: It still doesn't work. There's a missing `)` on line 3, but even when that's fixed, you still have an undefined `route` variable. Please when writing JS/HTML/CSS solutions, if at all possible, create a [snippet](https://meta.stackoverflow.com/q/269753/1243641) to demonstrate it working. – Scott Sauyet Oct 30 '20 at 14:50
@ScottSauyet sorry fot that..Added the necessary changes. and it seems to work fine – Malik Bagwala Oct 31 '20 at 04:46
@mailk: There is requested output in the question. This doesn't match it, not even close. The accepted answer and several others here do. I think if you're going to come late to the game, you really should get a solution that matches the requirements. – Scott Sauyet Nov 01 '20 at 15:07

score 1 · Answer 6 · answered Oct 31 '20 at 11:59

Array.prototype.flatMap is a good fit for recursive filtering. Similar to map, filter and reduce, using flatMap does not modify the original input -

const findHits = (t = []) =>
  t.flatMap(({ value, children }) => {
    if (value.startsWith("Hit"))
      return [{ value, children }]
    else {
      const r = findHits(children)
      return r.length ? [{ value, children: r }] : []
    }
  })

const input =
  [{value:'Miss1',children:[{value:'Miss2'},{value:'Hit1', children:[{value:'Miss3'}]}]},{value:'Miss4',children:[{value:'Miss5'},{value:'Miss6', children:[{value:'Hit2'}]}]},{value:'Miss7',children:[{value:'Miss8'},{value:'Miss9', children:[{value:'Miss10'}]}]},{value:'Hit3',children:[{value:'Miss11'},{value:'Miss12', children:[{value:'Miss13'}]}]},{value:'Miss14',children:[{value:'Hit4'},{value:'Miss15', children:[{value:'Miss16'}]}]}]

const result =
  findHits(input)

console.log(JSON.stringify(result, null, 2))

[
  {
    "value": "Miss1",
    "children": [
      {
        "value": "Hit1",
        "children": [
          {
            "value": "Miss3"
          }
        ]
      }
    ]
  },
  {
    "value": "Miss4",
    "children": [
      {
        "value": "Miss6",
        "children": [
          {
            "value": "Hit2"
          }
        ]
      }
    ]
  },
  {
    "value": "Hit3",
    "children": [
      {
        "value": "Miss11"
      },
      {
        "value": "Miss12",
        "children": [
          {
            "value": "Miss13"
          }
        ]
      }
    ]
  },
  {
    "value": "Miss14",
    "children": [
      {
        "value": "Hit4"
      }
    ]
  }
]

Yuri Gor · Answer 7 · 2019-03-07T23:02:54.693

0

Alternatively you can use _.filterDeep method from deepdash extension for lodash:

var keyword = 'Hit';
var foundHit = _.filterDeep(
  input,
  function(value) {
    return value.value.includes(keyword);
  },
  {
    tree: true,
    onTrue: { skipChildren: true },
  }
);

Here is a full test for your case

edited Mar 07 '19 at 23:02

answered Jan 15 '19 at 20:20

Yuri Gor

1,353
12
26

vincent · Answer 8 · 2021-05-10T15:33:43.180

Here is a different type of solution using object-scan.

This solution is iterative instead of recursive. It works because object-scan iterates in delete safe order. Basically we traverse into the tree and break on any match. Then we keep track of matches at the different depth (ensuring that we reset that information appropriately as we traverse into a neighbouring branches).

It's mostly an academic exercise as the recursive approach is cleaner and faster. However this answer might be interesting if there is additional processing that needs to be done or stack depth errors are a problem.

// const objectScan = require('object-scan');

const myInput = [{ value: 'Miss1', children: [{ value: 'Miss2' }, { value: 'Hit1', children: [{ value: 'Miss3' }] }] }, { value: 'Miss4', children: [{ value: 'Miss5' }, { value: 'Miss6', children: [{ value: 'Hit2' }] }] }, { value: 'Miss7', children: [{ value: 'Miss8' }, { value: 'Miss9', children: [{ value: 'Miss10' }] }] }, { value: 'Hit3', children: [{ value: 'Miss11' }, { value: 'Miss12', children: [{ value: 'Miss13' }] }] }, { value: 'Miss14', children: [{ value: 'Hit4' }, { value: 'Miss15', children: [{ value: 'Miss16' }] }] }];
const myFilterFn = ({ value }) => value.includes('Hit');

const rewrite = (input, filterFn) => objectScan(['**(^children$)'], {
  breakFn: ({ isMatch, value }) => isMatch && filterFn(value),
  filterFn: ({
    parent, property, key, value, context
  }) => {
    const len = (key.length - 1) / 2;
    if (context.prevLen <= len) {
      context.matches.length = context.prevLen + 1;
    }
    context.prevLen = len;

    if (context.matches[len + 1] === true || filterFn(value)) {
      context.matches[len] = true;
      return false;
    }
    parent.splice(property, 1);
    return true;
  },
  useArraySelector: false,
  rtn: 'count'
})(input, { prevLen: 0, matches: [] });

console.log(rewrite(myInput, myFilterFn)); // returns number of deletions
// => 8

console.log(myInput);
// => [ { value: 'Miss1', children: [ { value: 'Hit1', children: [ { value: 'Miss3' } ] } ] }, { value: 'Miss4', children: [ { value: 'Miss6', children: [ { value: 'Hit2' } ] } ] }, { value: 'Hit3', children: [ { value: 'Miss11' }, { value: 'Miss12', children: [ { value: 'Miss13' } ] } ] }, { value: 'Miss14', children: [ { value: 'Hit4' } ] } ]

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

<script src="https://bundle.run/object-scan@16.0.0"></script>

Disclaimer: I'm the author of object-scan

score 0 · Answer 9 · answered Nov 06 '21 at 16:03

Was looking for another way to solve this problem without directly mutating the children array and came up with this:

const input = [
  {
    value: 'Miss1',
    children: [
      { value: 'Miss2' },
      { value: 'Hit1', children: [ { value: 'Miss3' } ] }
    ]
  },
  {
    value: 'Miss4',
    children: [
      { value: 'Miss5' },
      { value: 'Miss6', children: [ { value: 'Hit2' } ] }
    ]
  },
  {
    value: 'Miss7',
    children: [
      { value: 'Miss8' },
      { value: 'Miss9', children: [ { value: 'Miss10' } ] }
    ]
  },
  {
    value: 'Hit3',
    children: [
      { value: 'Miss11' },
      { value: 'Miss12', children: [ { value: 'Miss13' } ] }
    ]
  },
  {
    value: 'Miss14',
    children: [
      { value: 'Hit4' },
      { value: 'Miss15', children: [ { value: 'Miss16' } ] }
    ]
  },
];

const filtered = input.reduce(function fr(acc, curr) {
  
  if (curr.children) {
    const children = curr.children.reduce(fr, []);
    if (children.length) {
        return acc.concat({ ...curr, children: children });
    }
  }
  if (curr.value.includes('Hit')) {
    return acc.concat(curr);
  } else {
    return acc;
  }
}, []);

console.log(filtered);

Recursively filter array of objects

9 Answers9

Linked

Related