Searching Through a Nested Object Using Recursion, Regular Expressions, and Sets
Tags: javascript, regex, recursion, objects
Published: 2020-03-11 01:17:23

Suppose you have a nested object, which would look something like this:

```javascript
const animals = [
  { id: 1,
    type: 'cat',
    pets: [
      { id: 1,
        name: 'Toby',
        breed: 'Tabby'
      }, 
      { id: 2,
        name: 'Golden Girl',
        breed: 'Russian Blue'
      }
    ]  
  },
  { id: 2,
    type: 'dog',
    pets: [
      { id: 3,
        name: 'Goldilocks',
        breed: 'Poodle'
      }
    ]
  },
  { id: 3,
    type: 'fish',
    pets: [
      { id: 4,
        name: 'Marigold',
        breed: 'Goldfish'
      }
    ]
  }
]

```

Let's say you were tasked with finding the number of pets who have 'gold' somewhere in their name, breed, or type. Just by looking at the object, you could probably answer that question pretty quickly--pet number 2, whose name is Golden Girl, pet number 3, whose name is Goldilocks, and number 4, who is a Goldfish. The answer would therefore be 3. But if this list were hundreds or thousands of items long, you'd need a better method.


### Laying out the Structure

When considering how to tackle this kind of problem, it's important to have a clear understanding of what your functions will do from the start. I think the best way to handle this sort of nested object is with recursion--because some keys are objects themselves (i.e. 'pets'), you need a way to iterate through every key until you can check the values as strings.

The first thing I'm going to do is create a global variable called 'result'. Result will store the matches to the search term, and needs to be placed in the global scope because it will be used by multiple functions.

Next, I'm going to create a function called 'getEachItem', which will take in the object. I want to first split up the 'animals' object into larger chunks, which are each of the animal groups. Then, with each of those items, I'm going to pass it into a function called 'searchItem', which will be the heart of this problem.

```javascript
const searchTerm = "gold"

let result = []

//this function will take separate out each item from the larger object
function getEachItem(object) {
  //...
};

//this function will search through each of the items returned from getEachItem
function searchItem(item) {
  //...
}

```

## Separating Out The Larger Object

The first thing that needs to be done is parsing through the animals object and getting each item from it, which is going to be in the getEachItem function.

One way to do that is by using a forEach loop. Once inside the loop, the second function, searchItem, will be called, and that item will be passed into it as an argument.

```javascript
const searchTerm = "gold"
let result = []

function getEachItem(object) {
  object.forEach(item => {
    searchItem(item)
  })
  //...
};

function searchItem(item) {
  //...
}

```

However, getEachItem is not finished at this stage. Once we're done writing searchItem, we'll come back to getEachItem with the results.

## Searching Through an Object with Recursion

Now that we have one item at a time, we will pass that item into the searchItem function. We need to go through each key in the item and check its value. One way to do that is by using `Object.keys()`. Object.keys() takes in an object and returns an array of the keys of that object. With that array, we can then do a forEach loop and check the value at each key.

The tricky thing with nested objects is that some values--but not all--are objects themselves. That means we need to use recursion to iterate through _those_ values, and do so until we the value is a string. Here, we can use `typeof` to check if the value at each key is an object. If it is, we will call the function over again--recursion.

```javascript
const searchTerm = "gold"
let result = []

function getEachItem(object) {
  object.forEach(item => {
    searchItem(item)
  })
  //...
};

function searchItem(item) {
  Object.keys(item).forEach(key => {
    if (typeof item[key] === "object") {
      searchItem(item[key])
    }
    //...
  })
}

```

If the item[key] is a string, that means we can check to see if that string contains our search term. This is a great place to use Regular Expressions. Regular expressions can easily be used with variables. In our example, we will create a new regular expression with the construction `new RegExp()`. Because we want to search for _all_ instances of the search term, and we also do not care about matching the case, we can append "gi" to the search term (g is for global match, i is for case-insensitive).

We then can use the `.match()` method, passing in the regular expression. If any part of the value at that key includes the search term, we know that's a match. We therefore can push that item's id to the result array.

The reason we push the item's id to the result array is so that, before we return the final count, we can check to see if there are any redundancies. For example, if there's a Goldfish whose name is Goldie, that should count as 1 pet rather than 2. 

```javascript
const searchTerm = "gold"
let result = []

function getEachItem(object) {
  object.forEach(item => {
    searchItem(item)
  })
  //...
};

function searchItem(item) {
  Object.keys(item).forEach(key => {
    if (typeof item[key] === "object") {
      searchItem(item[key])
    }
    if (typeof item[key] === "string") {
      let searchAsRegEx = new RegExp(searchTerm, "gi");
      if (item[key].match(searchAsRegEx)) {
        result.push(item.id)
      }
    }
  })
}

```

## Compile the Unique Results

As I mentioned above, we want to be sure we only return unique pets. A great way to remove duplicates is by using a set. Sets are similar to arrays, yet their elements must be unique.

Once searchItem is finished running, and the `result` array has elements in it, we can return to the getEachItem function. We can create a new set using `...new Set()`. Finally, we can return the length of that set, which is the number of pets that contain the search term.

```javascript
const searchTerm = "gold"
let result = []

function getEachItem(object) {
  object.forEach(item => {
    searchItem(item)
  })
  let uniqueResults = [...new Set(result)]
  return uniqueResults.length
};

function searchItem(item) {
  Object.keys(item).forEach(key => {
    if (typeof item[key] === "object") {
      searchItem(item[key])
    }
    if (typeof item[key] === "string") {
      let searchAsRegEx = new RegExp(searchTerm, "gi");
      if (item[key].match(searchAsRegEx)) {
        result.push(item.id)
      }
    }
  })
}

```

-----------------------

Let me know if you have any questions or alternate ways of solving this kind of problem in the comments below.