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.

Solution 1

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;
}

Solution 2

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);

Solution 3

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))

Solution 4

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));

Solution 5

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"
      }
    ]
  }
]

View more solutions

Comments

[Nathan Power]

Thanks, this approach actually made clearer to me where I was going wrong

[Scott Sauyet]

Please submit existing solutions to other problems only if they actually solve the problem at hand; the question has nothing to do with routes 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.

[Malik Bagwala]

@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.

[Scott Sauyet]

@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 to demonstrate it working.

[Malik Bagwala]

@ScottSauyet sorry fot that..Added the necessary changes. and it seems to work fine

[Scott Sauyet]

@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.

[Raphael Pinel]

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'