## Pages

### 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

// Edges

/* 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);

}```

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?