Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
I guess this requires printing the tree in spiral form.
1. Start with root.
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
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();
}
}
Here is my solution in C#, using two lists.
public static void PrintEvenOdd(TNode root)
{
bool isOdd = false;
List<TNode> prevNodes = new List<TNode>();
prevNodes.Add(root);
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)
currNodes.Add(node.left);
if (node.right != null)
currNodes.Add(node.right);
}
if (isOdd)
currNodes.Reverse();
PrintNodes(currNodes);
prevNodes.Clear();
if (isOdd)
currNodes.Reverse();
prevNodes.AddRange(currNodes);
}
}
private static void PrintNodes(List<TNode> list)
{
foreach (TNode node in list)
{
Console.Write(node.data + " ");
}
Console.WriteLine();
}
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
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
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++;
}
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);
}
}
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
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);
}
}
}
@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);
}
}
}
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);
}
}
}
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;
}
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);
}
How about this?
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;
}
}
queue q = new queue();
q.add(root)
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);}
}
}
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
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)
deque.addLast(node.left);
if (node.right != null)
deque.addLast(node.right);
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();
}
}
This can be solved with 2 stacks.
- cypher October 22, 20121. 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