DFS and BFS algorithms in trees with C#

In this article, I’m going to explain the DFS and BFS algorithms. Firstly, to understand well this article, you must have some basic knowledge about the tree data structure. When talking about trees, you should know they are hierarchical data structures, composed of two sets of elements – Nodes and Edges. The data is kept in the nodes, and the edges, represent the node connections. A good example of a tree data structure is a company hierarchy. For instance, If you build an organizational chart, you will probably represent it with a tree. When working with trees, DFS and BFS algorithms are usually used for searching.

Depth-First Search (DFS)

In this section, I’m going to explain the Depth-First Search (DFS) algorithm. The goal is to go as far down as possible, starting from the root, and then going over the other nodes. The successors of each node are visited with priority:

This algorithm can be implemented using a stack, following these steps:

• Firstly, add the root (9) to the stack
• Secondly, get the first child of 9 – it is 7
• Continue with adding 7 in the stack and get its first child – 25
• After that, add 25 to the stack – it DOESN’T have children, so remove 25 from the stack and go back to 7
• Then, get the next child of 7 – it is 72
• Continue with adding 72 in the stack – it doesn’t have children, so remove from the stack and go back to 7
• Get the next child of 7 – it is 8
• Add 8 to the stack – it doesn’t have children – remove from the stack and go back to 7
• 7 doesn’t have any more children, so remove from the stack and go back to 9
• Next child of 9 is 14 – add in the stack
• 14 doesn’t have children. Therefore, remove it from the stack and go back to 9
• After that, get the next child of 9 – 3 and add to the stack
• Continue with the next child of 3 – 1 and add to the stack
• 1 doesn’t have children, so remove from the stack and go back to 3
• After that, get the next child of 3 – 19 and add to the stack
• 19 doesn’t have children so remove from the stack and go back to 3
• 3 doesn’t have children – remove from stack and go back to 9
• Finally, 9 doesn’t have children – remove from the stack

Breadth-First Search (BFS)

In this section, I’m going to explain the Breadth-First Search (BFS) algorithm. As the name suggests, it is the opposite of DFS, where the idea is to go as far as possible in depth. Here the traversal is made in rows, starting from the root:

Can be implemented with a queue, following these steps:

• First of all, add the root 9 in the queue
• Until 9 has children – add all of them to the queue – 7, 14 and 3
• No more children for 9. Therefore, remove it from the queue and go to the next queue element – 7
• Continue with adding all children of 7 to the queue – 25, 72 and 8
• 7 is out of children, so remove it from the queue and go to the next element in the queue – 14
• It doesn’t have any children. Therefore, remove from the queue and go to 3
• Add all children of 3 to the queue – 1 and 19
• After that, remove 3 from the queue and go to the next element – 25
• No children for 25. Therefore, remove from the queue and go to 72
• No children for 72. Therefore, remove from the queue and go to 8
• No children for 8. Therefore, remove from the queue and go to 1
• No children for 1. Therefore, remove from the queue and go to 19
• And finally, no children for 19, so remove it from the queue

Demo with C#

In this section, I’m going to show how to implement both algorithms using C#. First of all, we have a class Node:

internal class Node<T>
{
    public IEnumerable<Node<T>> Children { get; set; }
    public T Data { get; set; }

    public Node(T data, params Node<T>[] children)
    {
        this.Data = data;
        this.Children = children;
    }
}

Each node keeps generic Data and a collection of children (sub-nodes). In other words, a sample tree can be created like this:

var tree = new Node<int>(9,
                new Node<int>(7, new Node<int>(25), new Node<int>(72), new Node<int>(8)),
                new Node<int>(14),
                new Node<int>(3, new Node<int>(1), new Node<int>(19)));

            //                     9
            //
            //         7           14          3
            //
            //  25    72    8             1       19

In this example, the root node is 9, and it has children – 7, 14, and 3. 7 has its own children 25, 72 and 8, 14 doesn’t have any children and 3 has 1 and 19.

For the DFS algorithm, we can use this function, for instance:

public static void DFSTraverse<T>(Node<T> node, Stack<Node<T>> s = null)
{
      s = s ?? new Stack<Node<T>>();
      s.Push(node);
      foreach (var item in node.Children)
      {
          DFSTraverse(item, s);
      }

      Console.WriteLine(s.Pop().Data);
  }

First of all we are pushing the first node 9 in a stack. After that, for each child node, we recursively call the function DFSTraverse, and pass to it the current state of the stack. This recursion will occur until the node doesn’t have any children, so then – just print it on the console. In this way we get the numbers printed in their traversal order.

For the BFS algorithm, we can use a queue. For instance:

public static void BFSTraverse<T>(Node<T> node)
{
    var q = new Queue<Node<T>>();
    q.Enqueue(node);

    while (q.Count > 0)
    {
        node = q.Dequeue();
        Console.WriteLine(node.Data);
        foreach (var item in node.Children)
        {
            q.Enqueue(item);
        }
    }
}

This algorithm will iterate by adding each row in a queue. When the whole row is added, it will start to remove from the queue and print the node data to the console.

As a result from the two algorithms, we get this output:

Finally, this is the order in which the tree was traversed, using the DFS and BFS algorithms.