Today I want to talk about computer science riddles versus computer science problems especially during job interviews. I will start by saying I hate CS riddles, I don't understand why someone would give them in an interview and what it would show about both the interviewer and the interviewee. On the other hand I love CS problems which made me wonder what is the difference between the two. I thought long and hard about this question and decided that the main difference is that a CS riddle is usually solved using a very specific, usually unorthodox method which in many times is not directly related to the topic (or general area) of the question. On the other hand a CS problem can be solved in many ways which usually derive from well known practices in CS.
Anyway... My story starts one day when I wondered into the kitchen at work seeking a cup of tea. I saw one of my group mates interviewing some guy. At this point he left the room to let the interviewee deal with the question alone so I took the opportunity to ask what was the question. He said that he asked the interviewee to print a binary tree using a BFS traversal. This is after he already solved the same question using the DFS traversal. I responded that this is a nice warm-up question since the two methods differ only by the words Stack (for DFS) and Queue (for BFS) and other than that the algorithm is exactly the same. He said that the interviewee solved the DFS traversal using recursion so he may have to think.
At this point I could leave the kitchen and concentrate on drinking my tea but I thought to myself... What is the difference between the recursive DFS and BFS methods?
Thinking further I realized that it is not that simple to implement a recursive BFS method because essentially the recursion uses a Stack while BFS uses a queue which are the opposite.
For the sake of this exercise I assume that a recursive method cannot use any loops of any kind and all the traversal must be done using the recursion.
I implemented a small tree class as follows:
public class TreeNode
{
public int Data
{
get;
set;
}
public TreeNode Left
{ get; set; }
public TreeNode Right
{ get; set; }
public TreeNode(int data)
{
Data = data;
}
}
public class Tree
{
public TreeNode Root
{
get;
set;
}
First I will present the iterative DFS and BFS methods (just to prove my point that they differ in only that one word) internal void PrintDfs() {
Console.Out.WriteLine("Printing tree using iterative DFS algorithm");
Stack<TreeNode> nodes = new Stack<TreeNode>();
nodes.Push(Root);
while (nodes.Count > 0)
{
TreeNode tempNode = nodes.Pop();
Console.Out.Write(string.Format("{0},", tempNode.Data));
if (tempNode.Right != null)
nodes.Push(tempNode.Right);
if (tempNode.Left != null)
nodes.Push(tempNode.Left);
}
Console.Out.WriteLine();
}
internal void PrintBfs()
{
Console.Out.WriteLine("Printing tree using iterative BFS algorithm");
Queue<TreeNode> nodes = new Queue<TreeNode>();
nodes.Enqueue(Root);
while (nodes.Count > 0)
{
TreeNode tempNode = nodes.Dequeue();
Console.Out.Write(string.Format("{0},", tempNode.Data));
if (tempNode.Left != null)
nodes.Enqueue(tempNode.Left);
if (tempNode.Right != null)
nodes.Enqueue(tempNode.Right);
}
Console.Out.WriteLine();
}Implementing DFS using recursion is trivial: private void PrintDfsRecursiveInternal(TreeNode node)
{
Console.Out.Write(string.Format("{0},", node.Data));
if (node.Left != null)
PrintDfsRecursiveInternal(node.Left);
if (node.Right != null)
PrintDfsRecursiveInternal(node.Right);
}
internal void PrintDfsRecursive()
{
Console.Out.WriteLine("Printing tree using recursive DFS algorithm");
PrintDfsRecursiveInternal(Root);
Console.Out.WriteLine();
}
Now what about implementing BFS using recursion. Well, I read a bit online and I tend to believe that it is impossible to do it in O(1) extra space therefore I will show a solution with O(n) extra space. Before I present my solution I would like to note a solution I found online here:BFS(Q)
{
if (|Q| > 0)
v <- Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)
BFS(Q)
}There is something very bad in this solution (and in fact all other solution I saw). Because the recursive call is at the end of the method the recursion level is O(n) while the recursion level of the DFS algorithm is only O(log(n)). Considering the fact that opening a stack frame is somewhat expensive, this makes a major difference.
My solution uses the regular DFS traversal but ignores the nodes from the DFS order and calculated the nodes from the BFS order passed by the queue to the recursive method.
internal void PrintBfsRecursive() { Console.Out.WriteLine("Printing tree using recursive BFS algorithm"); Queue<TreeNode> queue = new Queue<TreeNode>(); queue.Enqueue(Root); PrintBfsRecursiveInternal(queue, Root); Console.Out.WriteLine(); } private void PrintBfsRecursiveInternal(Queue<TreeNode> queue, TreeNode node) { if (queue.Count > 0) { TreeNode tempNode = queue.Dequeue(); Console.Out.Write(string.Format("{0},", tempNode.Data)); if (tempNode.Left != null) queue.Enqueue(tempNode.Left); if (tempNode.Right != null) queue.Enqueue(tempNode.Right); } if (node.Left != null) PrintBfsRecursiveInternal(queue,node.Left); if (node.Right != null) PrintBfsRecursiveInternal(queue, node.Right); }
As you can see I used the DFS traversal only as a counter for the iterative BFS algorithm but this saves me the exponential increase in stack size.
In any case, if you are interested in CS problems (not riddles) I suggest checking out this site: Project Euler (if you want to collaborate with me on this please email me)
Thanks for reading,Boris.
