Tree Graph Ordered Traversal Level by Level in C#



Recently as part of a job interview process, I was asked to solve some programming problems. This post shows the solution for one of such problems.

Problem
The problem ( or could we call it an algorithm exercise? ) is this:

Consider a tree of integers. Knowing that its root node is 0, and given its adjacency list as a two dimensional array of integers, write a function that prints out the elements/nodes in order/level by level starting from the root. That is, the root is printed in the first line, elements that can be reached from the root by a path of distance 1 in the second line, elements reached by a path of distance 2 in the third line, and so forth. For example, given the following adjacency list (draw the tree for a better view):

0 => 1, 2, 3
1 => 0, 4
2 => 0
3 => 0, 5
4 => 1, 6
5 => 3
6 => 4

The program should print:

0
1 2 3
4 5
6

Little bit of theory
If you read about Tree in Graph theory, you’ll see that we can represent a tree using a graph because a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree.

The tree in this problem isn’t a binary tree, it’s a n-ary tree.

Solution
With theory in mind, here goes my proposed solution…

I’m reusing some code from past posts. In special, the Graph, AdjacencyList, Node, NodeList and EdgeToNeighbor classes.

I use this method to fill a Graph with the Tree structure:

/// <summary>
/// Fills a graph with a given tree structure.
/// </summary>
/// <param name="graph"></param>
private static void FillGraphWithTreeStructure(Graph graph)
{
    // Vertexes
    graph.AddNode("0", null);
    graph.AddNode("1", null);
    graph.AddNode("2", null);
    graph.AddNode("3", null);
    graph.AddNode("4", null);
    graph.AddNode("5", null);
    graph.AddNode("6", null);

    // Edges
    graph.AddDirectedEdge("0", "1");
    graph.AddDirectedEdge("0", "2");
    graph.AddDirectedEdge("0", "3");

    graph.AddDirectedEdge("1", "4");

    graph.AddDirectedEdge("4", "6");

    graph.AddDirectedEdge("3", "5");

    /* This is the tree:
               
            0
          / | \
         1  2  3
        /       \
       4         5
      /
     6
             
        This is the expected output:
             
        Level 1 = 0
        Level 2 = 1 2 3
        Level 3 = 4 5
        Level 4 = 6

    */
}

This is the method that does the hard work:

/// <summary>
/// Performs an ordered level-by-level traversal in a n-ary tree from top-to-bottom and left-to-right.
/// Each tree level is written in a new line.
/// </summary> 
/// <param name="root">Tree's root node</param>
public static void LevelByLevelTraversal(Node root)
{
    // At any given time each queue will only have nodes that
    // belong to a level
    Queue<Node> queue1 = new Queue<Node>();
    Queue<Node> queue2 = new Queue<Node>();

    queue1.Enqueue(root);

    while (queue1.Count != 0 || queue2.Count != 0)
    {
        while (queue1.Count != 0)
        {
            Node u = queue1.Dequeue();

            Console.Write(u.Key);

            // Expanding u's neighbors in the queue
            foreach (EdgeToNeighbor edge in u.Neighbors)
            {
                queue2.Enqueue(edge.Neighbor);
            }
        }

        Console.WriteLine();

        while (queue2.Count != 0)
        {
            Node v = queue2.Dequeue();

            Console.Write(v.Key);

            // Expanding v's neighbors in the queue
            foreach (EdgeToNeighbor edge in v.Neighbors)
            {
                queue1.Enqueue(edge.Neighbor);
            }
        }

        Console.WriteLine();
    }
}

To spice things up I have implemented a Parallel version of the above method using a ConcurrentQueue:

/// <summary>
/// Performs an ordered level-by-level traversal in a n-ary tree from top-to-bottom and left-to-right in Parallel using a ConcurrentQueue.
/// Each tree level is written in a new line.
/// </summary> 
/// <param name="root">Tree's root node</param>
public static void LevelByLevelTraversalInParallel(Node root)
{
    // At any given time each queue will only have nodes that
    // belong to a level
    ConcurrentQueue<Node> queue1 = new ConcurrentQueue<Node>();
    ConcurrentQueue<Node> queue2 = new ConcurrentQueue<Node>();

    queue1.Enqueue(root);

    while (queue1.Count != 0 || queue2.Count != 0)
    {
        while (queue1.Count != 0)
        {
            Node u;
                    
            queue1.TryDequeue(out u);

            Console.Write(u.Key);

            // Expanding u's neighbors in the queue
            foreach (EdgeToNeighbor edge in u.Neighbors)
            {
                queue2.Enqueue(edge.Neighbor);
            }
        }

        Console.WriteLine();

        while (queue2.Count != 0)
        {
            Node v;
                    
            queue2.TryDequeue(out v);

            Console.Write(v.Key);

            // Expanding v's neighbors in the queue
            foreach (EdgeToNeighbor edge in v.Neighbors)
            {
                queue1.Enqueue(edge.Neighbor);
            }
        }

        Console.WriteLine();
    }
}

Now it’s time to measure the execution time using a StopWatch:

private static void Main(string[] args)
{
    Graph graph = new Graph();

    FillGraphWithTreeStructure(graph);

    Stopwatch stopWatch = new Stopwatch();

    stopWatch.Start();

    LevelByLevelTraversal(graph.Nodes["0"]);

    stopWatch.Stop();

    // Write time elapsed
    Console.WriteLine("Time elapsed: {0}", stopWatch.Elapsed);

    //Resetting the watch...
    stopWatch.Reset();

    stopWatch.Start();

    LevelByLevelTraversalInParallel(graph.Nodes["0"]);

    stopWatch.Stop();

    // Write time elapsed
    Console.WriteLine("Time elapsed: {0}", stopWatch.Elapsed);

    Console.ReadKey();
}

Now the results:

Sequential
0
1 2 3
4 5
6
Time elapsed: 00:00:00.0040340

Parallel
0
1 2 3
4 5
6
Time elapsed: 00:00:00.0020186

As you see, time is cut by a factor of 2. I currently have a Core 2 Duo processor in my Mac mini.

Hope you enjoy it and feel free to add your 2 cents to improve this code! Of course there are other ways of solving this very problem and I would like to see those other ways. Do you have any other better idea?

Download
You can get the Microsoft Visual Studio Console Application Project at:

https://sites.google.com/site/leniel/blog/TreeLevelTraversal.rar

To try out the code you can use the free Microsoft Visual C# 2010 Express Edition that you can get at: http://www.microsoft.com/visualstudio/en-us/products/2010-editions/visual-csharp-express