Recursive Filter on Nested array

Question

I need to filter a nested structure, that looks like this, based on query. I need to return all objects, including the parent object of the subtree, which match the query string in object name. Please help, i am stuck.

[
   {
     name: 'bob',
     type: 1,
     children: [
       {
         name: 'bob',
         type: 2,
         children: [
           {
             name: 'mike',
             type: 3,
             children: [ 
               {
                 name:'bob',
                 type: 7,
                 children: []
               },
               {
                 name: 'mike',
                 type: 9,
                 children: []
               }
             ]
           }
         ]
       },
       {
         name: 'mike',
         type: 2
       }
     ]
   }
 ]

Right now i am able to find a match in the tree recursively, but the function returns the object on the first match and does not search deeper on sub levels in the same object. Any suggestions, how i can modify the code to go search through all levels recursively?

  return tree.map(copy).filter(function filterNested(node) {
    if (node.name.toLowerCase().indexOf(query) !== -1) {
      return true;
    }

    if (node.children) {
      return (node.children = node.children.map(copy).filter(filterNested))
        .length;
    }
  });

if I am searching for query 'bob', the expected result should be,

 const arr = [
   {
     name: 'bob',
     type: 1,
     children: [
       {
         name: 'bob',
         type: 2,
         children: [
           {
             name: 'mike',
             type: 3,
             children: [ 
               {
                 name:'bob',
                 type: 7
               },
  
             ]
           }
         ]
       },
     ]
   }
 ]

Nina Scholz · Accepted Answer · 2019-10-29 21:52:25Z

10

You could reduce the array and build new objects with optional children, if they have a length not zero.

function filter(array, fn) {
    return array.reduce((r, o) => {
        var children = filter(o.children || [], fn);
        if (fn(o) || children.length) r.push(Object.assign({}, o, children.length && { children }));
        return r;
    }, []);
}

var data = [{ name: 'bob', type: 1, children: [{ name: 'bob', type: 2, children: [{ name: 'mike', type: 3, children: [{ name: 'bob', type: 7 }, { name: 'same', typ: 9 }] }] }, { name: 'mike', type: 2 }] }],
    result = filter(data, ({ name }) => name.toLowerCase() === 'bob');

console.log(result);

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

edited Oct 29, 2019 at 21:52

answered Oct 29, 2019 at 21:03

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Ruzihm Over a year ago

Ooh, that's a really neat trick with Object.assign({}, o, children.length && { children }). Kudos.

Curious Over a year ago

Thank you so much Mrs. Scholz. You are brilliant. Could you maybe walk me through how your function works, please?

Nina Scholz Over a year ago

@YordanRadev, because of being a recursive approach, you could look ta first to the exit condition which stops the recursion. here i is hidden in the empty array o.children || []. this prevents to run forever, because an empty array with reduce returns the startValue.

Nina Scholz Over a year ago

by having this in mind, the following parts is stright forward. the function takes two arguments, one an data array and the other a function wich has a condition, of the object contains the wanted proerty with a certain value. Then it takes the filterd children and checks the object or children length, only then it adds a new object to the result set.

Jacob · Accepted Answer · 2019-10-29 21:10:19Z

1

Something like this, perhaps?

function nestedFilter(query, nodes) {
  return nodes.reduce((result, node) => {
    const filteredChildren = node.children && nestedFilter(query, node.children);
    const nameMatches = node.name.toLowerCase().indexOf(query) !== -1;
    const childrenMatch = filteredChildren && filteredChildren.length;
    const shouldKeep = nameMatches || childrenMatch;
    return shouldKeep 
      ? result.concat({ ...node, children: filteredChildren }) 
      : result;    
  }, []);
}

edited Oct 29, 2019 at 21:10

answered Oct 29, 2019 at 21:04

Jacob

79k24 gold badges159 silver badges245 bronze badges

Comments

Ruzihm · Accepted Answer · 2019-10-29 21:18:17Z

You can use a recursive reduce for this, where you check if there are any children or if the name matches before you accumulate the object:

const example = [{
  name: 'bob',
  type: 1,
  children: [{
      name: 'bob',
      type: 2,
      children: [{
        name: 'mike',
        type: 3,
        children: [{
            name: 'bob',
            type: 7,
            children: []
          },
          {
            name: 'mike',
            type: 9,
            children: []
          }
        ]
      }]
    },
    {
      name: 'mike',
      type: 2
    }
  ]
}];

function reduceName(accum, item, matcher) {
  item.children = (item.children || []).reduce((a,i)=>reduceName(a,i,matcher),[]);
  if (!item.children.length) delete item.children;
  if (matcher(item) || item.children) accum.push(item);
  return accum;
}

console.log(example.reduce((a,i)=>reduceName(a,i,x=>x.name==='bob'),[]));

Edin Omeragic · Accepted Answer · 2019-10-29 21:35:25Z

I would just use good old visitor pattern to traverse and build new tree.

class Visitor {
    constructor(predicate) {
        this.predicate = predicate;
    }

    visit(item) {
        if (Array.isArray(item)) {
            return this.visitArray(item);
        } else if (item) {
            return this.visitItem(item);
        }
    }

    visitArray(item) {
        const result = [];
        for (let e of item) {
            const item = this.visit(e);
            if (item) {
                result.push(item);
            }
        }
        return result;
    }

    visitItem(item) {
        const children = this.visit(item.children);
        const hasChildren = (children && children.length > 0);

        if (hasChildren || this.predicate(item)) {
            return {
                name: item.name,
                type: item.type,
                children: children
            }
        }
        return null;
    }
}


const visitor = new Visitor((item) => item.name === "bob");
const result = visitor.visit(data);

console.log(result);

Mulan · Accepted Answer · 2020-06-08 15:26:53Z

A wonderful time to learn about mutual recursion and continuation passing style

const data =
  [{name:'bob',type:1,children:[{name:'bob',type:2,children:[{name:'mike',type:3,children:[ {name:'bob',type:7,children:[]},{name:'mike',type:9,children:[]}]}]},{name:'mike',type:2}]}]

const identity = x => x

const search = (all = [], query = identity, pass = identity) =>
  all.flatMap(v => search1(v, query, pass))

const search1 = (one = {}, query = identity, pass = identity) =>
  query(one)
    ? pass([ { ...one, children: search(one.children, query) } ])
    : search
        ( one.children
        , query
        , children =>
            children.length === 0
              ? pass([])
              : pass([ { ...one, children } ])
        )

const result =
  search(data, x => x.name === "bob")

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

Nathan Adda · Accepted Answer · 2020-06-08 05:59:41Z

0

I do think that this question will always be relevant so here is how I did it ! After a few hours ;)

var res = yourArray.filter(function f(el) {
    if (el.children.length > 0) {
        el.children = el.childreb.filter(f);
    }
    if (el.name === "bob") return true; // you can put the condition you need here.
})
//res is your returned array

Trully hope this code will benefit some of youl :)

answered Jun 8, 2020 at 5:59

Nathan Adda

11 silver badge2 bronze badges

1 Comment

Scott Sauyet Over a year ago

But note that the OP was looking to also include the bob inside the mike object. This technique needs to be more sophisticated to handle that.

Collectives™ on Stack Overflow

Recursive Filter on Nested array

6 Answers 6

4 Comments

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

4 Comments

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related