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?

Hallah

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.

Anabantid

Answer 2

you can do it recursively

public IEnumerable<IContent> BuildContentFrom(IEnumerable<Node> nodes) {
     foreach(var node in nodes){
         yield node;
         foreach(var c in BuildContentFrom(node.children)){
             yield c;
         }
     }
}

This might become a problem with n-trees when n is large and/or the tree deep. in which case you could use an accumulator

public IEnumerable<IContent> BuildContentFrom(IEnumerable<Node> nodes) {
     if(!nodes.Any()) return Enumerable.Empty<IContent>();
     var acc = new List<IContent>();
     BuildContentFrom(nodes);
}

public IEnumerable<IContent> BuildContentFrom(IEnumerable<Node> nodes, 
                                              IList<IContent> acc) {
     foreach(var node in nodes){
         acc.Add(BuildContentFromSingle(node));
         if(node.children.Any()) BuildContentFrom(node.children, acc);
     }
}

Which is now tail recursive and if the compiler optimizes for that (a setting for C# as far as I remember) you will have no stack issues even with large trees.

Alternatively you can use a stack to collect the work you still need to perform

public IEnumerable<IContent> BuildContentFrom(IEnumerable<Node> nodes)
{
    var stack= new Stack<Node>(nodes);

    while (stack.Any())
    {
        var next = stack.Pop();
        yield return BuildContentFromSingle(next);

        foreach (var child in next.Children)
        {
            stack.push(child);
        }
    }
}

Arras

Answer 3

As an alternative, you could consider flattening the structure using recursion. Here's an example with a binary tree. It demonstrates a depth-first flattening traversal.

using System;
using System.Collections.Generic;

namespace Demo
{
    public static class Program
    {
        static void Main(string[] args)
        {
            var tree = buildTree(5, true);
            printTree1(tree);
            Console.WriteLine("---------------------------------------------");
            printTree2(tree);
        }

        // Print tree using direct recursion.

        static void printTree1<T>(Node<T> tree)
        {
            if (tree != null)
            {
                Console.WriteLine(tree.Value);
                printTree1(tree.Left);
                printTree1(tree.Right);
            }
        }

        // Print tree using flattened tree.

        static void printTree2<T>(Node<T> tree)
        {
            foreach (var value in flatten(tree))
            {
                Console.WriteLine(value);
            }
        }

        // Flatten tree using recursion.

        static IEnumerable<T> flatten<T>(Node<T> root)
        {
            if (root == null)
            {
                yield break;
            }

            foreach (var node in flatten(root.Left))
            {
                yield return node;
            }

            foreach (var node in flatten(root.Right))
            {
                yield return node;
            }

            yield return root.Value;
        }

        static Node<string> buildTree(int depth, bool left)
        {
            if (depth > 0)
            {
                --depth;
                return new Node<string>(buildTree(depth, true), buildTree(depth, false), "Node." + depth + (left ? ".L" : ".R"));
            }
            else
            {
                return new Node<string>(null, null, "Leaf." + (left ? "L" : "R"));
            }
        }
    }

    public sealed class Node<T>
    {
        public Node(Node<T> left, Node<T> right, T value)
        {
            _left  = left;
            _right = right;
            _value = value;
        }

        public Node<T> Left  { get { return _left;  } }
        public Node<T> Right { get { return _right; } }
        public T       Value { get { return _value; } }

        private readonly Node<T> _left;
        private readonly Node<T> _right;
        private readonly T       _value;
    }
}

For your specific example, I think (without testing it) that you can do this:

public static IEnumerable<Node> Flatten(Node root)
{
    foreach (var node in root.Children)
    {
        foreach (var child in Flatten(node))
        {
            yield return child;
        }
    }

    yield return root;
}

Depending on whether you allow null nodes, you might need to add some null checking:

public static IEnumerable<Node> Flatten(Node root)
{
    if (root != null)
    {
        foreach (var node in root.Children)
        {
            foreach (var child in Flatten(node))
            {
                if (child != null)
                {
                    yield return child;
                }
            }
        }

        yield return root;
    }
}

Kendall