Tips for Maximizing the Efficiency of a Search in a Complexly Nested Object

I am faced with a complex JavaScript object structure that represents hierarchical data. This object contains multiple levels of nested children, and I have the task of searching for a specific value within this intricate structure. Let's take a look at an example of such a nested object:

 const data = {
  id: 1,
  name: "Root",
  children: [
    {
      id: 2,
      name: "Child 1",
      children: [
        {
          id: 3,
          name: "Grandchild 1",
          children: []
        },
        {
          id: 4,
          name: "Grandchild 2",
          children: []
        }
      ]
    },
    {
      id: 5,
      name: "Child 2",
      children: [
        {
          id: 6,
          name: "Grandchild 3",
          children: []
        }
      ]
    }
  ]
};

Currently, I have implemented a recursive function to search for a particular value based on its ID:

 function searchById(node, id) {
  if (node.id === id) {
    return node;
  }
  if (node.children) {
    for (let child of node.children) {
      const result = searchById(child, id);
      if (result) {
        return result;
      }
    }
  }
  return null;
}

const result = searchById(data, 4);
console.log(result);

Answer №1

When it comes to performing a single search, performance is not a major concern.

However, if you find yourself needing to search the same nested object multiple times, consider creating a secondary object that maps each id to its corresponding result. This way, you can populate the second object at once, simplifying all future searches.

In the following example, the generator function getEntriesRecursive iterates through the nested data structure and yields pairs of [id, node]. By converting these pairs into an object with keys as the ids, searching becomes as easy as accessing a property:

function* getEntriesRecursive(node) {
    yield [node.id, node];
    for (const child of node.children) {
        yield* getEntriesRecursive(child);
    }
}

// Example
const data = {id: 1,name: "Root",children: [{id: 2,name: "Child 1",children: [{id: 3,name: "Grandchild 1",children: []},{id: 4,name: "Grandchild 2",children: []}]},{id: 5,name: "Child 2",children: [{id: 6,name: "Grandchild 3",children: []}]}]};
const byId = Object.fromEntries(getEntriesRecursive(data));

for (const id of [4, 6, 5]) {
    console.log(id, byId[id]);
}

Answer №2

Enhance your search speed by loading multiple items into a map structure:

const data = {id: 1,name: "Root",children: [{id: 2,name: "Child 1",children: [{id: 3,name: "Grandchild 1",children: []},{id: 4,name: "Grandchild 2",children: []}]},{id: 5,name: "Child 2",children: [{id: 6,name: "Grandchild 3",children: []}]}]};

const map = new Map;
const traverse = item => (map.set(item.id, item), item.children?.forEach(traverse));

traverse(data);

for (const id of [4, 6, 5]) {
    console.log(id, map.get(id));
}

A performance comparison benchmark:

` Chrome/124
--------------------------------------------------
User123;   ■ 1.00x | x1000000 155 163 164 164 177
Dev456      12.32x |  x100000 191 201 209 212 218
--------------------------------------------------`

Open in the unique playground

const data = {id: 1,name: "Root",children: [{id: 2,name: "Child 1",children: [{id: 3,name: "Grandchild 1",children: []},{id: 4,name: "Grandchild 2",children: []}]},{id: 5,name: "Child 2",children: [{id: 6,name: "Grandchild 3",children: []}]}];

// @benchmark User123;
const map = new Map;
const traverse = item => (map.set(item.id, item), item.children?.forEach(traverse));

traverse(data);
[4, 6, 5].map(id => map.get(id));

// @benchmark Dev456
function* getEntriesRecursive(node) {
  yield [node.id, node];
  for (const child of node.children) {
      yield* getEntriesRecursive(child);
  }
}

const byId = Object.fromEntries(getEntriesRecursive(data));
[4, 6, 5].map(id => byId[id]);

/*@skip*/ fetch('https://awesomecdn.com/loader.js').then(response => response.text().then(eval));

Similar questions

If you have not found the answer to your question or you are interested in this topic, then look at other similar questions below or use the search

To include a Material Icon in your React-Toastify notification

This is an example of code located in a specific folder. While trying to incorporate a material Icon, an error has been encountered. 'React' must be in scope when using JSX import { toast } from 'react-toastify'; import ErrorIcon from ...

FFmpeg: audio synchronization issue observed with simultaneous usage of xfade and acrossfade techniques

Experiencing an issue when attempting to concatenate 12 videos together and maintain the audio using xfade and acrossfade filters. Without the audio stream, the video encodes correctly, but when combining with audio, transitions hang and audio sync is off. ...

The timer freezes at one minute remaining

I encountered a problem with the jQuery countdown I created. Once the count reaches 01:00, it stops instead of continuing to 00:59 with minutes at 0. var start = $('#start'); var countMinutes = 2; var timer; start.on('click', function ...

Best and most cost-effective method for transferring and storing data on Google App Engine

Looking to cut down on traffic and storage costs on Google App Engine. Users complete a form by selecting from various options that are lines of text, such as "Waking up multiple times during the night," or "Sleeping less than 7 hours per night," or "Havi ...

extract objects from an array of objects based on a specified array

Within my JSON array, I have data structured like this: const data = [ { "uniqueId": 1233, "serviceTags": [ { "Id": 11602, "tagId": "FRRRR", "missingRequired&quo ...

Enhance your viewing experience with the Zoom feature that activates when

I recently noticed on that I am able to zoom/enlarge a photo by clicking on it. Is there a way for me to incorporate this feature without purchasing the entire theme? While I understand the theme is designed for purchase, I only need this specific functi ...

The JSON array is not defined when looping through the second iteration

I'm having an issue with my JSON data containing URLs to pictures and corresponding numbers. When running it through two for loops, the first loop works fine, but the second one shows 'undefined'. Any ideas why? { "sources": [ ...

Click event doesn't trigger the 'else if' statement in jQuery

Having trouble with a button click issue. In the following code, when the button is clicked, it checks if the text on the button is "day". If so, it changes the background-color of the body to red and updates the button text to "night". I am struggling wit ...

Which method would be more efficient for initializing a member: a member initializer or assigning in the constructor?

class X { public: int x; X(int y) { x = y; } }; OR class Y { public: int y; Y(int z):y(z){} }; Which implementation would lead to faster object initialization? Will the generated code be the same for both, resul ...

Implementing data updates in Vue.js within a Mongoose database, along with making API

I've encountered an issue where I need to update a count variable representing the votes each video receives after using GET and POST functions to retrieve and save URLs in my database. Additionally, I'm looking to disable the voting button once ...

Encountering Issues with Discord JS as Member Fetch Returns Undefined

I'm facing an issue with fetching specific server members by their user id in order to assign a role to them. I keep getting an undefined response each time. Even though this bot has administrator permission and all required intents are assigned, I a ...

The Bootstrap accordion feature or show/hide function is experiencing issues when dealing with dynamically created elements in jQuery

When interacting with items in my sample application, a pop-up displaying the item's description should appear. However, attempts to use Bootstrap accordion or hide and show features were unsuccessful, only jQuery delegate event handlers worked. In g ...

JSHow to dynamically access child elements in objects

I am facing a challenge in dynamically accessing a JSObject item: jsonElement = { name:"name", subElement { subElementName: "nameSubElement", } } Currently, I have the element as: //level = "name" jsonElement[level] -> it works //lev ...

Typescript is throwing a Mongoose error stating that the Schema has not been registered for the model

I've dedicated a lot of time to researching online, but I can't seem to figure out what's missing in this case. Any help would be greatly appreciated! Permission.ts (This is the Permission model file. It has references with the Module model ...

Confused by loops? I could use some assistance

I'm having trouble figuring out how to make this JavaScript code block repeat itself. This code is for a code-operated Phidget switch that controls an electronic relay by turning it on and off with a timer for a specific duration. The "Phidget22" Node ...

Displaying preprocessing before downloading on the frontend side

Let me walk you through the process first - A user initiates a download request (jsp) Based on the user's parameters (in spring mvc controller mapping), a single excel workbook is created by merging multiple other excel sheets (~40). The final workb ...

Ways to include Bootstrap Tooltips on an input field that has the type of "file"

I attempted the code below: <input type="file" name="file" id="fileField" data-toggle="tooltip" data-placement="bottom"/> <script> $(document).ready(function() { $('[data-toggle="tooltip"]').tooltip(); }); </script> ...

Retrieve class attributes within callback function

I have integrated the plugin from https://github.com/blinkmobile/cordova-plugin-sketch into my Ionic 3 project. One remaining crucial task is to extract the result from the callback functions so that I can continue working with it. Below is a snippet of ...

Exploring the method of inserting an element into a nested array using JavaScript's ES6 features

Let's say I understand how to use the spread operator to add an element to a regular array in ES6. const arr = ["a","b"] const newArr = [...arr, "c"] This would result in ["a","b","c"] But when it comes to implementing this with a nested array, like ...

Adjustable height within embedded object tag

I've been struggling to adjust the height of the content on my site automatically. I have attempted using iframes as well, but nothing seems to work despite trying numerous code examples from various sources including CSS and JS scripts. Any help wou ...