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