Using Async/Await to recursively traverse a tree in TypeScript

Question

Using Async/Await to recursively traverse a tree in TypeScript

Here is the basic tree structure I am working with:

class Group {
  id: ObjectId;
  name: string;
  subGroups: [ObjectId]
}

https://i.sstatic.net/woZFs.jpg

For instance, Group A contains Group B and C as subGroups, while Group C has subGroups F, G, H, and so on.

I am in need of implementing an algorithm to recursively fetch all groups:

Expected Output = [Group A, Group B, Group C, Group D, Group E, Group F, Group G, Group H, Group I, Group J]

However, I require fetching the subGroups asynchronously from the database using async/await.

Approach 1

    const tr = async (group: Group, result: Group[]) => {
      console.log(group);
      result.push(group);
      for (const id of group.subGroups) {
        const groupId = id.toHexString();
        const subGroup = this.findGroup(groupId);
        tr(await subGroup, result);
      }
    };

    const result = [];
    await tr(user.group, result);
    console.log(result);

Approach 2

  async transverse(group: Group, result: Group[]) {
    console.log(group);
    result.push(group);
    for (const id of group.subGroups) {
      const groupId = id.toHexString();
      const subGroup = await this.findGroup(groupId);
      await this.transverse(subGroup, result);
    }
  }

  const result = [];
  await transverse(user.group, result);
  console.log(result);

Approach 1 fails to provide the correct array output and does not include Groups A to J. Approach 2 achieves the desired array, but the code lacks cleanliness. Can someone suggest an elegant solution to accomplish this task and explain why approach 1 falls short?

javascript typescript recursion async-await tree

Answer 1

Answer №1

If you want to enhance your tree traversal process, consider incorporating modern features such as an async generator.

Given that the example demonstrates a breadth-first traversal, opting for iteration instead of recursion would be more suitable. By looping through each level of the tree, Group objects on the same level can be resolved in "parallel" since their outcomes are independent of each other. This scenario is perfect for utilizing Promise.all rather than using individual awaits for each node separately.

Let's visualize how this implementation could appear by including a simulated database component:

class Group {
    constructor(id, subGroups) {
        this.id = id;
        this.subGroups = subGroups;
    }
}

// Simulated asynchronous DB operations
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));
const db = {
    _tree: {
        "A": ["B", "C"],
        "B": ["D", "E"],
        "C": ["F", "G", "H"],
        "D": [],
        "E": [],
        "F": ["I", "J"],
        "G": [],
        "H": [],
        "I": [],
        "J": []
    },
    async findGroup(groupId) {
        await delay(Math.random() * 1000);
        return new Group(groupId, db._tree[groupId]);
    }
};

// Establish an async generator function
async function* tr(groupId) {
    let result = [await db.findGroup(groupId)];
    while (result.length) {
        yield* result;
        // Follow a Breadth-first traversal approach and introduce some parallelism
        result = await Promise.all(result.flatMap(group => group.subGroups.map(db.findGroup)));
    }
};

// Consume the results from the async iterator generated by the above function. Begin by passing the ID of the root of the tree:
(async () => {
    for await (const result of tr("A")) {
        console.log(result);
    }
})();

Answer 2

If you want to enhance your tree traversal process, consider incorporating modern features such as an async generator.

Given that the example demonstrates a breadth-first traversal, opting for iteration instead of recursion would be more suitable. By looping through each level of the tree, Group objects on the same level can be resolved in "parallel" since their outcomes are independent of each other. This scenario is perfect for utilizing Promise.all rather than using individual awaits for each node separately.

Let's visualize how this implementation could appear by including a simulated database component:

class Group {
    constructor(id, subGroups) {
        this.id = id;
        this.subGroups = subGroups;
    }
}

// Simulated asynchronous DB operations
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));
const db = {
    _tree: {
        "A": ["B", "C"],
        "B": ["D", "E"],
        "C": ["F", "G", "H"],
        "D": [],
        "E": [],
        "F": ["I", "J"],
        "G": [],
        "H": [],
        "I": [],
        "J": []
    },
    async findGroup(groupId) {
        await delay(Math.random() * 1000);
        return new Group(groupId, db._tree[groupId]);
    }
};

// Establish an async generator function
async function* tr(groupId) {
    let result = [await db.findGroup(groupId)];
    while (result.length) {
        yield* result;
        // Follow a Breadth-first traversal approach and introduce some parallelism
        result = await Promise.all(result.flatMap(group => group.subGroups.map(db.findGroup)));
    }
};

// Consume the results from the async iterator generated by the above function. Begin by passing the ID of the root of the tree:
(async () => {
    for await (const result of tr("A")) {
        console.log(result);
    }
})();

Answer 3

Answer №2

Alright, let's take a look at your class structure

class Group {
  id: ObjectId;
  name: string;
  subGroups: [ObjectId]
}

We must clarify our requirements so, The anticipated outcome should be:

[Group A, Group B, Group C, Group D, Group E, Group F, Group G, Group H, Group I, Group J

In essence, we need to iterate in the following manner: group -> all children and repeat.

We can utilize a variable to store the upcoming groups and then iterate over them. This variable will be initialized with the first group that is fetched (For instance, group A) and subsequently the loop will display its name, iterate through its children, and preserve each child to be next in the print-to variable we created earlier. Once we finish iterating through its children, we will eliminate the primary group.

We will incorporate a while loop that will only terminate when the nextToPrint variable is an empty array.

nextToPrint = []; // variable to hold the next groups to print so it will need to be initialized with groupA.


// some method that runs when your app starts, like mounted() on Vue, attached() on aureliaJS or ngOnInit on Angular
async someMethod() {
  const first = await getGroup(first) // obtain the first group
  nextToPrint.push(first); // add to the queue-like variable


  // iterate through the next to print 
  while(nextToPrint.length) {
      printGroup(nextToPrint[0]); // display the first item in the next list
  }
}

async printGroup(group: Group) {
   console.log(group.name); // display Group name
   group.subGroups.forEach(g => {
       const child = await getGroup(g); // retrieve the next group
       nextToPrint.push(child); // include child to be the last one to print
       console.log(child.name); // show the child name
   });

   nextToPrint.shift(); // remove the first element from the next to print
}

I hope this explanation assists you. Please don't hesitate to leave comments or ask additional questions until we achieve the desired outcome

Answer 4

Alright, let's take a look at your class structure

class Group {
  id: ObjectId;
  name: string;
  subGroups: [ObjectId]
}

We must clarify our requirements so, The anticipated outcome should be:

[Group A, Group B, Group C, Group D, Group E, Group F, Group G, Group H, Group I, Group J

In essence, we need to iterate in the following manner: group -> all children and repeat.

We can utilize a variable to store the upcoming groups and then iterate over them. This variable will be initialized with the first group that is fetched (For instance, group A) and subsequently the loop will display its name, iterate through its children, and preserve each child to be next in the print-to variable we created earlier. Once we finish iterating through its children, we will eliminate the primary group.

We will incorporate a while loop that will only terminate when the nextToPrint variable is an empty array.

nextToPrint = []; // variable to hold the next groups to print so it will need to be initialized with groupA.


// some method that runs when your app starts, like mounted() on Vue, attached() on aureliaJS or ngOnInit on Angular
async someMethod() {
  const first = await getGroup(first) // obtain the first group
  nextToPrint.push(first); // add to the queue-like variable


  // iterate through the next to print 
  while(nextToPrint.length) {
      printGroup(nextToPrint[0]); // display the first item in the next list
  }
}

async printGroup(group: Group) {
   console.log(group.name); // display Group name
   group.subGroups.forEach(g => {
       const child = await getGroup(g); // retrieve the next group
       nextToPrint.push(child); // include child to be the last one to print
       console.log(child.name); // show the child name
   });

   nextToPrint.shift(); // remove the first element from the next to print
}

I hope this explanation assists you. Please don't hesitate to leave comments or ask additional questions until we achieve the desired outcome

Using Async/Await to recursively traverse a tree in TypeScript

Answer №1

Answer №2

Similar questions

Using Formik with MUI Multiple Select

I need to save the API response in object form from Angular so that I can use it later. Can someone suggest the best way to store this response efficiently?

Can data be transferred using ajax upon clicking a button and then utilizing the data in a form on the same page?

The function useNuxtApp() in Nuxt 3 is returning an unknown type

Is it possible to use both parameters and callback functions in the MongoDB update() function in tandem?

Locate the final element within an array using JavaScript

Why is it that when a boolean value is logged as a checkbox, it shows up as undefined?

TranslateY animation glitching

Utilizing TypeScript interfaces with additional parameter object members does not result in the anticipated compilation error

Modifying a variable within an arrow function does not result in the variable being changed when checked outside of the arrow

Run numerous React applications simultaneously for extended periods of time

Applying the jqtransform plugin to all forms except for one

Issue: "Stumbled upon an unknown provider! This often implies the presence of circular dependencies"

React element failing to appear on webpage

What is the best way to ensure that the buttons remain in place once they have been clicked to reveal a drop-down menu?

Tips for implementing a "load more" button to fetch the next 50 requests using axios

JavaScript fails to effectively validate URLs

Error messages are displayed when using Express, while Promise.allSettled successfully completes its tasks

javascript functionality may be affected in Internet Explorer and Firefox following the upgrade to jquery version 1.8.3

The error "marker.setMap not a function" was not caught in the Google Maps API