Skip to content

Instantly share code, notes, and snippets.

@xpando
Created July 21, 2012 00:41
Show Gist options
  • Select an option

  • Save xpando/3154042 to your computer and use it in GitHub Desktop.

Select an option

Save xpando/3154042 to your computer and use it in GitHub Desktop.
Extensions methods for iteratively traversing trees using Stack<T> and Queue<T>
public static class IterativeTreeExt
{
public static IEnumerable<T> AsDepthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> children)
{
var nodes = new Stack<T>(new [] { head });
while(nodes.Count > 0)
{
var currentnode = nodes.Pop();
foreach (var child in children(currentnode))
nodes.Push(child);
yield return currentnode;
}
}
public static IEnumerable<T> AsBreadthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> children)
{
var nodes = new Queue<T>(new[] { head });
while (nodes.Count > 0)
{
var currentnode = nodes.Dequeue();
foreach (var child in children(currentnode))
nodes.Enqueue(child);
yield return currentnode;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment