## Microsoft Interview Question for SDETs

• 1
of 1 vote

Team: Cloud
Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

Here's the simple C# code for both recursive and iterative in-order traversals. The maximum stack size is equal to the tree height. For an arbitrary tree it is equal to O(n) in the worst case. For a perfectly balanced BST it is equal to O(lgN).

``````using System;
using System.Collections.Generic;

namespace CareerCup
{
public class TreeNode
{

public TreeNode(int key, int value)
{
_key = key;
_value = value;
}

public int Key
{
get
{
return _key;
}
}

public int Value
{
get
{
return _value;
}
}

public TreeNode Left { get; set; }

public TreeNode Right { get; set; }
}

public class InorderTraversal
{
public void TraverseRecursively(TreeNode node, Action<TreeNode> callback)
{
if (node == null)
{
return;
}

TraverseRecursively(node.Left, callback);
callback(node);
TraverseRecursively(node.Right, callback);
}

public void TraverseIteratively(TreeNode node, Action<TreeNode> callback)
{
if (node == null)
{
return;
}

Stack<TreeNode> stack = new Stack<TreeNode>();
while (stack.Count > 0 || node != null)
{
if (node == null)
{
TreeNode parent = stack.Pop();
callback(parent);
node = parent.Right;
}
else
{
stack.Push(node);
node = node.Left;
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0

the question restricts to no recursion solutions

Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is my solution in C# assuming the tree is binary tree.
Regarding the max number of elements in stack at a time - height of the binary tree. Assuming the binary tree is balanced, it is log(n) where n is number if elements in the tree.

``````public static void InOrderWithoutStack(Node root)
{
if (root == null)
throw new ArgumentNullException("root");

Node temp = root;
Stack<Node> s = new Stack<Node>();

while (temp != null)
{
s.Push(temp);
temp = temp.Left;
}

while (s.Count != 0)
{
Node t = s.Pop();
System.Console.WriteLine(t.Value + " ");

if (t.Right != null)
{
t = t.Right;
while (t != null)
{
s.Push(t);
t = t.Left;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) I am assuming this is a Binary Tree to begin with

A simple non recursive (Iterative) approach is possible by trying to replace the recursion stack by our own stack, sort of a behavioral replication. Here are the steps:

a) Keep adding all the left nodes to the stack.
b) Once done with step 'a', pop the element from the stack and print it.
c) Once done with step 'b', add the node on the right of the popped element to the stack.
d) Repeat 'a','b','c' until the stack is empty & there are no elements left on the right.

The maximum size of the stack in the worst case would be O(n) as the height of the BT could be 'n' in the worst case.

Here's the java code:

``````/*
* Given the root of a BT. We must print the
* Inorder of this tree without recursion.
* The solution is O(n) time and O(n) space
* solution
*/
public void printInorderIterative(TreeNode root)
{

if(root==null)
return;

Stack<TreeNode> s= new Stack<TreeNode>();

TreeNode current= root;

while(!s.isEmpty() || current!=null)
{
while(current!=null)
{
s.push(current);
current=current.left;
}

if(!s.isEmpty())
{
current=s.pop();
System.out.print(current.element + " ");
current=current.right;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

This algorithm will not work as when you reach the left most node, the current will be assigned to null in the last line current = current.right and you will break out of the while look.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void nonrecursiveInorder(Node root) {
Stack<Node> queue = new Stack<>();
if (root == null)
throw new NullPointerException();
else {
while (!queue.isEmpty()) {
Node _temp = new Node();
_temp = queue.pop();
if (_temp.leftChild == null && _temp.rightChild == null) {
System.out.println(_temp.data);
} else {
if (_temp.visited == false) {
if (_temp.rightChild != null)
_temp.visited = true;
if (_temp.leftChild != null)
} else {
System.out.println(_temp.data);
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void InOrderTreeTraversal(TreeNode rootNode)
{
var treeStack = new Stack<TreeNode>();
treeStack.Push(rootNode);

while (treeStack.Count != 0)
{
var currentNode = treeStack.Pop();

if (currentNode != null &&
(currentNode.Left != null || currentNode.Right != null))
{
if (currentNode.Right != null) treeStack.Push(currentNode.Right);

treeStack.Push(currentNode);
treeStack.Push(null);

if (currentNode.Left != null) treeStack.Push(currentNode.Left);

}
else
{
if (currentNode == null && treeStack.Count > 0)
currentNode = treeStack.Pop();

Console.Write("{0} ", (char)currentNode.Data);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void print(node *root, int N) {
node* stk[N];
int stkSize=1,num[N];
stk=root;
num=0;
while (stkSize) {
root=stk[stkSize];
if (root==NULL) {
stkSize--;
continue;
}
if (num[stkSize]==0) {
num[stkSize]++;
stkSize++;
stk[stkSize]=root->left;
num[stkSize]=0;
}
else if (num[stkSize]==1) {
printf("%d ",root->val);
num[stkSize]++;
stkSize++;
stk[stkSize]=root->right;
num[stkSize]=0;
}
else if (num[stkSize]==2) stkSize--;

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

void print(node *root)
{
stack st;
if(root) st.push(root);
while(!st.empty())
{
if (root->left)
{
st.push(root->left);
root = root->left;
continue;
}

print st.top();
pop();
while (!root->right)
{
//Backtrace
print st.top();
root = st.pop();
}
if(root->right)
{
st.push(root->right)
root
}
if (root->right)
{
st.push(root->right)
root = root->right
}
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.