Search nested array of objects and return whole path of all matching items

I would like to search a deeply nested array of objects and return the path of all matched objects. I have partial solution of the problem but the code returns path of only first matched object. Please have a look at the input, expected output and the code itself. I have commented the desired logic in the expected output section.

Thanks in advance. Please help me out.

The Input Data

   [
   {
      "label":"Home",
      "key":"home",
      "level":1,
      "children":[
         {
            "label":"Indoor Furniture",
            "key":"furniture",
            "level":2,
            "children":[
               {
                  "label":"Chair",
                  "key":"chair",
                  "level":3
               },
               {
                  "label":"Table",
                  "key":"table",
                  "level":3
               },
               {
                  "label":"Lamp",
                  "key":"lamp",
                  "level":3
               }
            ]
         }
      ]
   },
   {
      "label":"Outdoor",
      "key":"outdoor",
      "level":1,
      "children":[
         {
            "label":"Outdoor Furniture",
            "key":"furniture",
            "level":2,
            "children":[
               {
                  "label":"Trampoline",
                  "key":"trampoline",
                  "level":3
               },
               {
                  "label":"Swing",
                  "key":"swing",
                  "level":3
               },
               {
                  "label":"Large sofa",
                  "key":"large sofa",
                  "level":3
               },
               {
                  "label":"Medium Sofa",
                  "key":"mediumSofa",
                  "level":3
               },
               {
                  "label":"Small Sofa Wooden",
                  "key":"smallSofaWooden",
                  "level":3
               }
            ]
         },
         {
            "label":"Games",
            "key":"games",
            "level":2,
            "children":[
               
            ]
         }
      ]
   },
   {
      "label":"Refurbrished Items",
      "key":"refurbrished items",
      "level":1,
      "children":[
         
      ]
   },
   {
      "label":"Indoor",
      "key":"indoor",
      "level":1,
      "children":[
         {
            "label":"Electicity",
            "key":"electicity",
            "level":2,
            "children":[
               
            ]
         },
         {
            "label":"Living Room Sofa",
            "key":"livingRoomSofa",
            "level":2,
            "children":[
               
            ]
         }
      ]
   }
]

Expected Output – if sofa is searched

[
// Remove the entire object if label of the object itself or any of its children doesn't include sofa
      {
         "label":"Outdoor",
         "key":"outdoor",
         "level":1,
         "children":[
            {
               "label":"Indoor Furniture",
               "key":"indoorFurniture",
               "level":2,
               "children":[
// Remove unmatched siblings
                  { `// Child node matched, hence return its path from root (Outdoor -> Indoor Furniture)`  
                     "label":"Large sofa",
                     "key":"large sofa",
                     "level":3
                  },
                  { // Child node matched, hence return its path from root (Outdoor -> Indoor Furniture) and all its children if any
                     "label":"Medium Sofa",
                     "key":"mediumSofa",
                     "level":3
                  },
                  { // Child node matched, hence return its path from root (Outdoor -> Indoor Furniture) and all its children if any
                     "label":"Small Sofa Wooden",
                     "key":"smallSofaWooden",
                     "level":3
                  }
               ]
            }
         ]
      },
      {
         "label":"Indoor",
         "key":"indoor",
         "level":1,
         "children":[
            { // Child node matched, hence return its path from root (Indoor) and all its children if any
               "label":"Living Room Sofa",
               "key":"livingRoomSofa",
               "level":2,
               "children":[
                  
               ]
            }
         ]
      }
   ]

Expected Output – if furniture is searched

[ // Remove the entire object if label of the object itself or any of its children doesn't include furniture
          {
             "label":"Home",
             "key":"home",
             "level":1,
             "children":[
                { // Child node matched, hence return its path from root (Home) and all its children if any
                   "label":"Indoor Furniture",
                   "key":"indoorFurniture",
                   "level":2,
                   "children":[
                      {
                         "label":"Chair",
                         "key":"chair",
                         "level":3
                      },
                      {
                         "label":"Table",
                         "key":"table",
                         "level":3
                      },
                      {
                         "label":"Lamp",
                         "key":"lamp",
                         "level":3
                      }
                   ]
                }
             ]
          },
          {
             "label":"Outdoor",
             "key":"outdoor",
             "level":1,
             "children":[
                { // Child node matched, hence return its path from root (Outdoor) and all its children if any
                   "label":"Outdoor Furniture",
                   "key":"outdoorFurniture",
                   "level":2,
                   "children":[
                      {
                         "label":"Trampoline",
                         "key":"trampoline",
                         "level":3
                      },
                      {
                         "label":"Swing",
                         "key":"swing",
                         "level":3
                      },
                      {
                         "label":"Large sofa",
                         "key":"large sofa",
                         "level":3
                      },
                      {
                         "label":"Medium Sofa",
                         "key":"mediumSofa",
                         "level":3
                      },
                      {
                         "label":"Small Sofa Wooden",
                         "key":"smallSofaWooden",
                         "level":3
                      }
                   ]
                }
             ]
          }
       ]

The code

function findChild(obj, condition) {
if (Object.entries(condition).every( ([k,v]) => (obj[k].toLowerCase()).includes(v.toLowerCase()))) {
    return obj;
}
for (const child of obj.children || []) {
    const found = findChild(child, condition);
    // If found, then add this node to the ancestors of the result
    if (found) return Object.assign({}, obj, { children: [found] });
 }
}
var search = { label: 'sofa' };
console.log(findChild(input, search)); // It returns only the first matched item path, i would like to get all matched items path

Answer

This looks like it will do it:

const filterDeep = (pred) => (xs, kids) =>
  xs .flatMap (
    x => 
      pred (x)
        ? [x]
      : (kids = filterDeep (pred) (x .children || [])) && kids.length
        ? [{... x, children: kids}] 
      : []
    
  )

const testIncludes = (condition) => (obj) =>
  Object .entries (condition) .every (
    ([k, v]) => (obj [k] || '') .toLowerCase () .includes (v .toLowerCase ())
  )

const filterMatches = (obj, conditions) =>
  filterDeep (testIncludes (conditions)) (obj)


const input = [{label: "Home", key: "home", level: 1, children: [{label: "Indoor Furniture", key: "furniture", level: 2, children: [{label: "Chair", key: "chair", level: 3}, {label: "Table", key: "table", level: 3}, {label: "Lamp", key: "lamp", level: 3}]}]}, {label: "Outdoor", key: "outdoor", level: 1, children: [{label: "Outdoor Furniture", key: "furniture", level: 2, children: [{label: "Trampoline", key: "trampoline", level: 3}, {label: "Swing", key: "swing", level: 3}, {label: "Large sofa", key: "large sofa", level: 3}, {label: "Medium Sofa", key: "mediumSofa", level: 3}, {label: "Small Sofa Wooden", key: "smallSofaWooden", level: 3}]}, {label: "Games", key: "games", level: 2, children: []}]}, {label: "Refurbrished Items", key: "refurbrished items", level: 1, children: []}, {label: "Indoor", key: "indoor", level: 1, children: [{label: "Electicity", key: "electicity", level: 2, children: []}, {label: "Living Room Sofa", key: "livingRoomSofa", level: 2, children: []}]}]


console .log ('sofa:', filterMatches (input, {label: 'sofa'}))
console .log ('furniture:', filterMatches (input, {label: 'furniture'}))

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

We separate out the recursive filtering mechanism, and also the object-matching part, putting them back together in filterMatches. The idea is that we might want to filter by many means, so the function takes an arbitrary predicate function that can test the current node. testIncludes takes an object of key-value pairs and returns a function which takes an object and reports whether the object’ corresponding keys each includes the relevant value. (I added case-insensitive checking here based on your input / requested output combination.)

Note that I named the central function with the word filter rather than find, as find generally implies returning the first match, whereas filter is supposed to return all matches.

---

For my own use, I would structure the main function slightly differently:

const filterMatches = (conditions) => (obj) =>
  filterDeep (testIncludes (conditions)) (obj)

console .log ('sofa:', filterMatches ({label: 'sofa'}) (input))

I like these curried functions a great deal, and with the parameters in that order I feel they are most useful. But YMMV.

Update

A comment noted a lint failure for the main function. It’s an understandable one, as this did something tricky in using an assignment inside a conditional expression. So here are some working variants:

• Moving the assignment to a default parameter:

  const filterDeep = (pred) => (xs, kids) =>
    xs .flatMap (
      (x, _, __, kids = filterDeep (pred) (x .children || [])) => 
        pred (x)
          ? [x]
        : kids.length
          ? [{... x, children: kids}] 
        : [] 
    )
  

  Pros:

  • This keeps our expression-only style alive, and avoids the trickiness above.
  • It’s fairly easy to read

  Cons:

  • It uses default parameters, which have their problems.
  • It requires naming two unused parameters from flatMat (Here _ and __.)

• Using statement style:

  const filterDeep = (pred) => (xs, kids) =>
    xs .flatMap ((x) => {
      if (pred (x)) {
        return [x]
      }
      const kids = filterDeep (pred) (x .children || [])
      if (kids.length > 0) {
        return [{... x, children: kids}] 
      }
      return []
    })
  

  Pros:

  • No more trickiness of any sort
  • More accessible for beginners

  Cons:

  • if and return are statements and statements lead to less modular code than working with pure expressions.

• Using a call helper function:

  const call = (fn, ...args) => fn (...args)
  
  const filterDeep = (pred) => (xs, kids) =>
    xs .flatMap (
      (x) => 
        pred (x)
          ? [x]
        : call (
          (kids) => kids.length ? [{... x, children: kids}] : [], 
          filterDeep (pred) (x .children || [])
        )
    )
  

  Pros:

  • A call helper function is all-around useful and can be reused in many places.
  • It avoids any fiddling with parameters

  Cons:

  • This combines the last two clauses of what is really a three-part test (returning [x], returning [{... x, children: kids}], and returning []) into a single function

I have a slight preference for that last version. But any of them would do.