Depth first search using Queue

Question

How do I do a depth first search using a Queue in c#?

The following is my datastructure:

public class Node
{
  public string Name{get;set}
  public IEnumerable<Node> Children{get;set;}
}

Now I have a collection of Node object each with children, which again has children and so on.

I want to access each node and convert it into a different form.

Something like the below:

public IEnumerable<IContent> BuildContentFrom(IEnumerable<Node> nodes)
        {
            var queue = new Queue<Node>(nodes);

            while (queue.Any())
            {
                var next = queue.Dequeue();
                yield return BuildContentFromSingle(next);

                foreach (var child in next.Children)
                {
                    queue.Enqueue(child);
                }
            }
        }

        public IContent BuildContentFromSingle(Node node)
        {
            var content = _contentFactory.Create(node);
            return content;
        }  

The above does not give me depth first for some reason. Can you please help?

Answer 1

Depth-first search is implemented using a LIFO data structure, so you 'd need to swap the Queue for a Stack. Using a FIFO structure like a queue gives you BFS instead.