## Microsoft Interview Question for Software Engineer in Tests

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

This can be solved with 2 stacks.
1. Read the root node and add it to the stack "even".
2. pop nodes out of the stack even. Now, read the right child first and then left, print it and push it to stack "odd". Do this until the stack even is empty.
3. Now, pop nodes out of stack odd. Read the left child first and then right, print it and push it to stack "even". Do this until the stack odd is empty.
4. repeat 2 and 3 until it was an empty stack to begin with - this means that we traversed the last level in the previous step

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

can you give an implementation

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

I guess this requires printing the tree in spiral form.

2. Since root is at odd level (and next level will be even), add its children in reverse order to the queue, i.e. root.right and then root.left
3. Proceed similarly for other levels.

If we are adding children of a particular node, following rule should be considered
a. if node at even level, add node.left then node.right
b. if node at odd level, add node.right then node.left

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

but wouldn't this print 'a c d f g d e'

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

Yes you are right. There is some correction required in reversal of intermediate results.

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

static void print(Node root)
{
Stack<Node> odd = new Stack<Node>();
Stack<Node> even = new Stack<Node>();
odd.Push(root);
while (odd.Count != 0 || even.Count != 0)
{
while (odd.Count != 0)
{
Node node = odd.Pop();
if(node.left!=null)
even.Push(node.left);
if(node.right!=null)
even.Push(node.right);
Console.Write(node.data+" ");
}
Console.WriteLine();
while (even.Count != 0)
{
Node node = even.Pop();
if (node.right != null)
odd.Push(node.right);
if (node.left != null)
odd.Push(node.left);
Console.Write(node.data + " ");
}
Console.WriteLine();
}
}

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

Here is my solution in C#, using two lists.

``````public static void PrintEvenOdd(TNode root)
{
bool isOdd = false;
List<TNode> prevNodes = new List<TNode>();
PrintNodes(prevNodes);
List<TNode> currNodes = new List<TNode>();

while (prevNodes.Count > 0)
{
isOdd = !isOdd;
currNodes.Clear();

foreach (TNode node in prevNodes)
{
if (node.left != null)

if (node.right != null)
}
if (isOdd)
currNodes.Reverse();
PrintNodes(currNodes);
prevNodes.Clear();
if (isOdd)
currNodes.Reverse();

}
}

private static void PrintNodes(List<TNode> list)
{
foreach (TNode node in list)
{
Console.Write(node.data + " ");
}
Console.WriteLine();
}``````

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

but wouldn't that print 'a c b f g d e'

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

Yeah right..

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

I think a Broad First Search with a stack can solve this problem.
1. Add the root node to the queue.
2. Get the head node of the queue and add its children to the queue.
3. If the node is in even level, print it. Otherwise, push it into the stack
4. When level of the head node has changed from odd to even,pop the stack and print the node
5. Repeat from 2 until all the node have been scaned

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

another solution to this is to use "deque"

1. odd levels - print the node value from the bottom and push the child nodes to the top

2. even levels - print the node value from the top end and push the child nodes to the bottom

always pop the node after printing its value

also we will have a couple of O(1) memory - one to track the number of elements to print during the current print option and other one is for the number of elements in the next level.

Please correct me if I am wrong

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

``````vector< vector<tree *> > v;
vector<tree *>x;
x.push_back(root);
v.push_back(x);
int i=0;
while(!v[i].empty())
{
x.clear();
if(i%2==0)
{
for(int j=v[i].size()-1;j>=0;j--)
{
if(v[i][j]->left) x.push_back(v[i][j]->left);
if(v[i][j]->right) x.push_back(v[i][j]->right);
cout<<v[i][j]->info<<" ";
}
}
if(i%2!=0)
{
for(int j=v[i].size()-1;j>=0;j--)
{
if(v[i][j]->right) x.push_back(v[i][j]->right);
if(v[i][j]->left) x.push_back(v[i][j]->left);
cout<<v[i][j]->info<<" ";
}
}
v.push_back(x);
i++;
}``````

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

``````vector<node*> print_odd_level(vector<node*> nodes) {
for (int i=0; i<nodes.size(); i++)
cout << nodes[i]->value << " ";
return next_level(nodes);
}
vector<node*> print_even_level(vector<node*> nodes) {
for (int i=nodes.size()-1; i>=0; i--)
cout << nodes[i] << " ";
return next_level(nodes);
}
vector<node*> next_level(vector<node*> nodes) {
vector<node*> next;
for (int i=0; i<nodes.size(); i++) {
if (nodes[i]->left)
next.push_back(nodes[i]->left);
if (nodes[i]->right)
next.push_back(nodes[i]->right);
}
return next;
}

void print() {
if (!root) return;
vector<node*> nodes;
nodes.push_back(root);
int level = 1;
while (!nodes.empty()) {
if (level%2==1)
nodes = print_odd_level(nodes);
else
nodes = print_even_level(nodes);
}
}``````

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

Ans to Ques 1 :
Do a level order traversal using a queue.
Pseudocode

``````Enqueue(Q, root)
Enqueue(Q, NULL) //marker for level end
while (!isEmptyQueue(Q)) {
temp = Dequeue(Q);
if (temp == NULL) {
//marks end of level
//Pop all the elements and print
if (!isEmptyQueue(Q))
Enqueue(Q, NULL) //marker
}
Push(stack, temp);
if (temp->left)
Enqueue(Q, temp->left);
if (temp->right)
Enqueue(Q, temp->right);
}``````

The other question can be solved as well by making minor modifications

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

Code for Reverse Level Order for each Level procedure

``````#include <iostream>
#include <stack>
#include <queue>
using namespace std;

void ReverseLevelOrderForEachLevel(struct Node *root) {
struct Node *temp;
if(!root)
return;
queue<Node*> Q;
stack<Node*> S;
Q.push(root);
Q.push(NULL);
while (!Q.empty()) {
temp = Q.front();
Q.pop();
if (temp == NULL) {
while(!S.empty()) {
cout<<S.top()->data<<" ";
S.pop();
}
cout<<endl;
if(!Q.empty()) {
Q.push(NULL);
}
}
else {
S.push(temp);
if(temp->left)
Q.push(temp->left);
if(temp->right)
Q.push(temp->right);
}
}
}``````

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

@crystal.rishi2 above code is reversing order of nodes from level2

This is modified code of your version which is working fine

``````void BST::ReverseLevelOrderForEachLevel() {
Node *temp;
if(!root)
return;
queue<Node*> Q;
stack<Node*> S;
queue<Node*> Q1;
Q.push(root);
Q.push(NULL);
int level=1;
cout<<endl<<"custom Print2:"<<endl;
while (!Q.empty()) {
temp = Q.front();
Q.pop();
if (temp == NULL) {
if(level%2==0){
while(!S.empty()) {
cout<<S.top()->data<<" ";
S.pop();
}
}
else {
while(!Q1.empty()) {
cout<<Q1.front()->data<<" ";
Q1.pop();
}
}
cout<<endl;
if(!Q.empty()) {
Q.push(NULL);
level++;
}
}
else {
if(level%2==0)
S.push(temp);
else Q1.push(temp);
if(temp->left)	Q.push(temp->left);
if(temp->right)  Q.push(temp->right);
}
}
}``````

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

Hi Nikhil,

On a second thought, this question seems to asking for ZigZag Traversal of the tree. I hope I am correct. Following is the code for Zig Zag Traversal.

``````void ZigZagTraversal(struct Node *root) {
struct Node *temp;
int leftToRight = 1;
stack<Node*> current;
stack<Node*> next;

current.push(root);
while (!current.empty()) {
temp = current.top();
current.pop();
if (temp) {
cout<<temp->data<<" ";
if (leftToRight) {
if (temp->left)
next.push(temp->left);
if (temp->right)
next.push(temp->right);
}
else {
if (temp->right)
next.push(temp->right);
if (temp->left)
next.push(temp->left);
}
}
if (current.empty()) {
leftToRight ^=1;
std::swap(current, next);
}
}
}``````

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

``````public NodeQueue bfs(Node traverseNode, int level) {
NodeQueue nodeQueue = new NodeQueue();
NodeQueue resultQueue = new NodeQueue();
traverseNode.setLevel(1);
nodeQueue.push(traverseNode);
resultQueue.push(traverseNode);

while (!nodeQueue.isEmpty()) {

traverseNode = nodeQueue.pop();
level = traverseNode.getLevel();
level++;
if (traverseNode.getLeft() != null) {
traverseNode.getLeft().setLevel(level);
nodeQueue.push(traverseNode.getLeft());
//	resultQueue.push(traverseNode.getLeft());
}
if (traverseNode.getRight() != null) {
traverseNode.getRight().setLevel(level);
nodeQueue.push(traverseNode.getRight());
//	resultQueue.push(traverseNode.getRight());
}

if(level%2==0){
if (traverseNode.getRight() != null) {
resultQueue.push(traverseNode.getRight());
}
if (traverseNode.getLeft() != null) {
resultQueue.push(traverseNode.getLeft());
}
}
else
{
if (traverseNode.getLeft() != null) {
resultQueue.push(traverseNode.getLeft());
}
if (traverseNode.getRight() != null) {
resultQueue.push(traverseNode.getRight());
}
}

}
return resultQueue;
}``````

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

void LevelOrderTraval(BST *Node)
{
std::queue<BST*> QueueToHold;
QueueToHold.push(Node);

while(!QueueToHold.empty())
{
BST *tmp = QueueToHold.front();
QueueToHold.pop();
std::cout<< tmp->data <<"\n";

if (tmp->lChild)
QueueToHold.push(tmp->lChild);
if (tmp->rChild)
QueueToHold.push(tmp->rChild);
}

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

1. do an pre-oder and print values in an array also label then with their levels

a bdecfg
1233233

odd from tight and even from level .. level wise

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

``````public class OddEvenTreeTraversal {
private static void printTree(TreeNode root){
Stack<TreeNode> oddStack = new Stack<TreeNode>();
Stack<TreeNode> evenStack = new Stack<TreeNode>();
oddStack.push(root);
while(!oddStack.empty() || !evenStack.empty()){
while(!oddStack.empty()){
TreeNode n = oddStack.pop();
System.out.println(n.data);
if(n.left!=null)
evenStack.push(n.left);
if(n.right!=null)
evenStack.push(n.right);
}
while(!evenStack.empty()){
TreeNode n = evenStack.pop();
System.out.println(n.data);
if(n.right!=null)
oddStack.push(n.right);
if(n.left!=null)
oddStack.push(n.left);
}
}
}

public static void main(String[] argv){
TreeNode d = new TreeNode('d');
TreeNode e = new TreeNode('e');
TreeNode f = new TreeNode('f');
TreeNode g = new TreeNode('g');
TreeNode c = new TreeNode('c');
TreeNode b = new TreeNode('b');
TreeNode a = new TreeNode('a');
a.left = b;
a.right = c;
b.left = d;
b.right= e;
c.left = f;
c.right = g;
printTree(a);
}

}

class TreeNode{
char data;
TreeNode left;
TreeNode right;
public TreeNode(char data){
this.data = data;
}
}``````

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

queue q = new queue();
stack s = new stack();
while((isOdd && !q.empty())||(!isOdd && !s.empty())
{
if(isOdd)
{
whie(!q.isempty){Node n =e.dequeue; print(n);s.push(n.left);s.push(n.right);isodd=false;}
}
else
{
while(!s.empty){Node n = s.pop;print n;enque(n.left);n.enque(n.right);}
}
}

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

It reverses order of all the nodes of tree after level 1.

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

``````import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.Queue;

public class BSTPrint {
TreeNode root;

class TreeNode {
double value;
TreeNode left;
TreeNode right;

public TreeNode(double value) {
super();
this.value = value;
left = null;
right = null;
};

}

public void insert(double value) {
root = insertT(root, value);
}

public TreeNode insertT(TreeNode root, double value) {
if (root == null) {
TreeNode r = new TreeNode(value);
return r;
}
if (value > root.value) {
// right
root.right = insertT(root.right, value);
} else if (value < root.value) {
root.left = insertT(root.left, value);
}
return root;
}

public void inorder() {
inorderT(root);
System.out.println();
}

private void inorderT(TreeNode root) {
if (root == null) {
return;
}
inorderT(root.left);
System.out.print(root.value + "\t");
inorderT(root.right);
}

/**
* WAP to print the node values of a binary tree - Even level starting from
* right to left - Odd level starting from left to right Assume that level
* of root is 1.
*/
public void levelPrint() {
if (root == null) {
return;
}
Deque<TreeNode> deque = new ArrayDeque<TreeNode>();
deque.offerLast(root);
int level = 1;
while (!deque.isEmpty()) {
if (level % 2 == 1) {
for (Iterator<TreeNode> iterator = deque.iterator(); iterator
.hasNext();) {
System.out.print(iterator.next().value + " ");
}
} else {
for (Iterator<TreeNode> iterator = deque.descendingIterator(); iterator
.hasNext();) {
System.out.print(iterator.next().value + " ");
}
}
int size = deque.size();
while (size > 0) {
TreeNode node = deque.pollFirst();
if (node.left != null)
if (node.right != null)
size--;
}
level++;
}
}

public static void main(String[] args) {
BSTPrint bst = new BSTPrint();
bst.insert(6);
bst.insert(5);
bst.insert(4);
bst.insert(2);
bst.insert(8);
bst.insert(7);
bst.insert(3);
bst.insert(9);
bst.levelPrint();
}

}``````

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

Build a mapping between level and nodes: Do a BFS traverse, store following in a hashtable: key: level , value: list of nodes in level

do a foreach on hashtable print nodes for each level from first to last (or last to first) regarding odd (even) level.

Complexity: O(n)

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.