Method TraverseBreadthFirst

| Edit this page View Source

TraverseBreadthFirst<T>(T, Func<T, IEnumerable<T>>)

Traverses a tree in a breadth-first fashion, starting at a root node and using a user-defined function to get the children at each node of the tree.

Declaration
public static IEnumerable<T> TraverseBreadthFirst<T>(T root, Func<T, IEnumerable<T>> childrenSelector)
Parameters
Type Name Description
T root

The root of the tree to traverse.
Func<T, IEnumerable<T>> childrenSelector

The function that produces the children of each element.
Returns
Type Description
IEnumerable<T>

A sequence containing the traversed values.
Type Parameters
Name Description
T

The tree node type
Remarks

The tree is not checked for loops. If the resulting sequence needs to be finite then it is the responsibility of childrenSelector to ensure that loops are not produced.

This function defers traversal until needed and streams the results.

Examples

The following code example demonstrates how to traverse a tree breadth-first using TraverseBreadthFirst.

Node root = new(0,
[
    new(1), new(2), new(3),
    new(4,
    [
        new(5), new(6),
        new(7, [ new(8), new(9) ]),
        new(10, [ new(11) ]),
    ]),
    new(11),
    new(12,
    [
        new(13), new(14),
        new(15, [ new(16), new(17) ]),
        new(18),
    ]),
    new(19), new(20),
]);

// Traverse a tree
var result = SuperEnumerable
    .TraverseBreadthFirst(
        root,
        static x => x.Children ?? [])
    .Select(x => x.Id);

Console.WriteLine(
    "[" +
    string.Join(", ", result) +
    "]");

// This code produces the following output:
// [0, 1, 2, 3, 4, 11, 12, 19, 20, 5, 6, 7, 10, 13, 14, 15, 18, 8, 9, 11, 16, 17]

record Node(int Id, IEnumerable<Node>? Children = null);
Exceptions
Type Condition
ArgumentNullException

childrenSelector is null.