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
Figure 3 - The Parallel Stacks window in Visual Studio 2012 ( #8 threads )
