Microsoft Coding Question #1

I recently had the privilege of interviewing at Microsoft. I figured I'd post the technical questions and answers in case they might help someone out there.

So here is the first one:

Given a Binary Tree, provide a method to traverse it depth first. Print the value of each node to the console.

We will assume there are methods to get the root node of a tree (rootNode) and the left and right nodes of a node (leftNode, rightNode)

Ex:



Should print 2,3,1,4,5


Solution (Recursive):

public void printTree(BinaryTree tree)
{
   if(tree !=null)
       printNodes(tree.rootNode);
}

private void printNode(Node node)
{
   if(node != null)
   {
       Console.writeLine(node.data);
      printNode(node.leftNode);
       printNode(node.rightNode);
   }
}

Solution (Non-recursive):

public void printTree(BinaryTree tree)
{
    if(tree !=null)
    {
       Stack<binarytree.node> stack = new Stack<binarytree.node>;
       stack.Push(tree.rootNode);
       while (stack.Count != 0)
          {
          BinaryTree.Node          currentNode = stack.Pop();
          Console.WriteLine(currentNode.data);

          if             (currentNode.rightNode != null)
                stack.Push(currentNode.rightNode);
            if (currentNode.leftNode != null)
               stack.Push(currentNode.leftNode);             }
         }
      }