Abusing the microtask queue to create a recursive breadth-first search.

README.md

• DartPad
• JSFiddle

This gist contains Dart and JavaScript examples of using the microtask queue to implement a recursive breadth-first search. Normally, a recursive graph/tree search is depth-first, as it uses the call stack to keep track of the frontier. However, the event loop in JavaScript and, by extension, Dart, uses a queue, not a stack. The microtask queue in particular is good for a recursive pattern as it blocks up the entire event loop until every single microtask has been processed.

Interestingly, Dart actually gives much simpler control over which queue things go into. In JavaScript, Promises, and thus async functions, always resolve in the microtask queue, not the regular event queue, which is why the JavaScript implementation does not require anything extra to deal with which queue things get sent to. In Dart, however, Futures normally complete in the normal event queue, not the microtask queue, while a special constructor, Future.microtask(), can be used to stick it into the microtask queue. Streams seem to work very similarly. This results in much more clearly defined and more controllable behavior than the JavaScript version.

The JavaScript code is based on the original Dart code which took a predicate function and returned a Future<T?> instead of just streaming the nodes and letting the client do whatever it wants. Unfortunately, there isn't really an equivalent of a Stream in JavaScript, so that implementation still uses Promises.

main.dart

import 'dart:async';

class Tree<T> {
  const Tree({
    required this.value,
    this.left,
    this.right,
  });

  final T value;
  final Tree<T>? left;
  final Tree<T>? right;
}

Stream<T> dfs<T>(Tree<T> root) async* {
  final controller = StreamController<T>();
  Future<void> inner(Tree<T>? cur) async {
    if (cur == null) {
      return;
    }
    
    controller.add(cur.value);
    
    await inner(cur.left);
    await inner(cur.right);
  }

  inner(root).then((_) => controller.close());
  
  yield* controller.stream;
}

Stream<T> bfs<T>(Tree<T> root) async* {
  final controller = StreamController<T>();
  Future<void> inner(Tree<T>? cur) async {
    if (cur == null) {
      return;
    }
    
    controller.add(cur.value);

    Future.microtask(() => inner(cur.left));
    Future.microtask(() => inner(cur.right));
  }

  Future.microtask(() => inner(root));
  Future(() {
    // The microtask queue must be empty before any other events can be run. Because
    // of that, awaiting a regular event via the Future() constructor after at least
    // one microtask has been scheduled guarantees that it won't run until after the
    // queue has emptied.
    controller.close();
  });
  
  yield* controller.stream;
}

void main() async {
  final tree = const Tree(
    value: 1,
    left: Tree(
      value: 2,
      left: Tree(
        value: 3,
        left: Tree(
          value: 4,
        ),
      ),
      right: Tree(
        value: 5,
      ),
    ),
    right: Tree(
      value: 6,
      left: Tree(
        value: 7,
        left: Tree(
          value: 8,
        ),
      ),
      right: Tree(
        value: 9,
      ),
    ),
  );

  await for (final v in dfs(tree)) {
    print(v);
  }
  print('');
  
  await for (final v in bfs(tree)) {
    print(v);
  }
  print('');

  print('Done.');
}

main.js

const dfs = async (root, f) => await new Promise(async (resolve, reject) => {
  let resolved = false
  const inner = async (cur) => {
    if (cur == null) {
      return
    }
    if (resolved) {
      return
    }
    if (await f(cur.value)) {
      resolved = true
      resolve(cur.value)
      return
    }

    await inner(cur.left)
    await inner(cur.right)
  }

  await inner(root)
  resolve(null)
})

const bfs = async (root, f) => await new Promise(async (resolve, reject) => {
  let resolved = false
  const inner = async (cur) => {
    if (cur == null) {
      return
    }
    if (resolved) {
      return
    }
    if (await f(cur.value)) {
      resolved = true
      resolve(cur.value)
      return
    }

    inner(cur.left)
    inner(cur.right)
  }

  await inner(root)
  resolve(null)
})

;(async () => {
  const tree = {
    value: 1,
    left: {
      value: 2,
      left: {
        value: 3,
        left: {
          value: 4,
        },
      },
      right: {
        value: 5,
      },
    },
    right: {
      value: 6,
      left: {
        value: 7,
        left: {
          value: 8,
        },
      },
      right: {
        value: 9,
      },
    },
  }

  await dfs(tree, (v) => {
    console.log(v)
    return false
  })
  console.log()

  await bfs(tree, (v) => {
    console.log(v)
    return false
  })
  console.log()
})()