breadthFirstSearch method

T? breadthFirstSearch({ Iterable<T>? startingNodes, ValuePredicate<T>? descendCondition, ValuePredicate<T>? returnCondition, Visitor<T>? onTraverse, })

Traverses the subtrees of startingNodes in breadth first order. If startingNodes is not provided, roots will be used instead.

descendCondition is used to determine if the descendants of the node passed to it should be traversed. When not provided, defaults to a function that always returns true which leads to every node on the tree being visited by this traversal.

returnCondition is used as a predicate to decide if the iteration should be stopped. If this callback returns true the node that was passed to it is returned from this method. When not provided, defaults to a function that always returns false which leads to every node on the tree being visited by this traversal.

An optional onTraverse callback can be provided to apply an action to each visited node. This callback is called prior to returnCondition and descendCondition making it possible to update a node before checking its properties.

Implementation

T? breadthFirstSearch({
  Iterable<T>? startingNodes,
  ValuePredicate<T>? descendCondition,
  ValuePredicate<T>? returnCondition,
  Visitor<T>? onTraverse,
}) {
  descendCondition ??= (T _) => true;
  returnCondition ??= (T _) => false;
  final List<T> nodes = List<T>.of(startingNodes ?? roots);

  while (nodes.isNotEmpty) {
    final T node = nodes.removeAt(0);

    onTraverse?.call(node);

    if (returnCondition(node)) {
      return node;
    }

    if (descendCondition(node)) {
      nodes.addAll(childrenProvider(node));
    }
  }

  return null;
}