Async/Await for tree traversal recursively in TypeScript

Question

I have the simple tree structure as following:

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

For example, Group A has two subGroups Group B, C, and Group C has three subGroups Group F, G, H, etc.

I need to implement an algorithm to get all groups recursively: Expected Output = [Group A, Group B, Group C, Group D, Group E, Group F, Group G, Group H, Group I, Group J]

But I need to fetch the subGroups from the database so that that should be async/await.

Method 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);

Method 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);

Method 1 cannot output the correct array, and it does not output the completed Gourp A to J. Method 2 can get the correct array, but the code does not look clean. Does anyone know how to achieve this goal in an elegant way and answer me why method 1 doesn't work?

Answer 1

You could make use of some modern features, like an async generator, to do a traversal over your tree.

As in the example you have given, the traversal is breadth-first, I would not go for recursion, but iterate with a loop over each level of the tree. The Group objects can be resolved in "parallel" when they are on the same level, as these results don't depend on each other. This is a good use case for using Promise.all instead of individual awaits for each node separately.

Here is how it could look -- I have included an mock for the database part:

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

// Mock of asynchronous DB
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]);
    }
};

// Make an async generator
async function* tr(groupId) {
    let result = [await db.findGroup(groupId)];
    while (result.length) {
        yield* result;
        // Use Breadth-first traversal order, and allow some parallellism
        result = await Promise.all(result.flatMap(group => group.subGroups.map(db.findGroup)));
    }
};

// Consume the async iterator you get from the above function. The call starts with the id of the tree's root:
(async () => {
    for await (const result of tr("A")) {
        console.log(result);
    }
})();

Answer 2

Ok, so your class looks like

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

We need to define what we need so, Expected output is:

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

In other words, we need to loop in the following way: group -> all children and repeat.

We can use a variable that will hold the next groups and then loop through it. This variable will be initialized with the first group that you fetch (For example group A) and then the loop will print it name, loop through it children and will save each children to be next on the print-to variable we just made. After we finish to loop through it children, we will remove the main group.

We will use a while loop that will stop only when 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 starting, like mounted() on Vue, attached() on aureliaJS or ngOnInit on Angular
async someMethod() {
  const first = await getGroup(first) // get first group
  nextToPrint.push(first); // push to the queue-like variable


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

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

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

Hope it will help, feel free to comment and ask more questions until we get it right