async-dfs.md

// tree node type
type Node = {
  id: number;
  children: () => Promise<Node[]>
}

// results array
const results: Node[] = [];

Imagine a tree data structure where the children are retrieved asynchronously. The goal is to traverse this tree depth-first while achieving maximum parallelization. It is straightforward to write an implementation that simply awaits the children() when it's encountered:

async function traverseDepthFirst(root: Node): Promise<number[]> {
  const results: number[] = [];
  
  const stack: Node[] = [root];
  while (stack.length) {
    const { data, children } = stack.pop();
    results.push(data);
    
    for (const child of await children()) {
      stack.push(child);
    }
  }
  
  return results;
}

To parallelize this, it's possible to execute multiple node.children() async calls at the same time as long as they are on the same level in the tree. The difficulty with parallelizing the traversal is that these Promises may complete at any time, but we want the results array to respect DFS order.