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); }
}
}
