## Microsoft Interview Question

Country: India
Interview Type: In-Person

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

This is a very common but difficult interview question. This problem can be solved by using two stacks.

``````void postOrderTraversalIterativeTwoStacks(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
stack<BinaryTree*> output;
s.push(root);
while (!s.empty()) {
BinaryTree *curr = s.top();
output.push(curr);
s.pop();
if (curr->left)
s.push(curr->left);
if (curr->right)
s.push(curr->right);
}
while (!output.empty()) {
cout << output.top()->data << " ";
output.pop();
}
}``````

However to understand this concept more easily watch this wonderful video on youtube
youtu.be/hv-mJUs5mvU

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

Isn't this basically reverse of preorder? In which case, this is not right.

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

Actually no. This is not preorder.

We are doing right first, then left (notice the order of stack pushes). In that case, the reverse of that traversal is indeed the preorder.

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

last preorder = postorder.

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

``````void postOrderTraversalIterative(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
// we are traversing down the tree
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left) {
s.push(curr->left);
} else if (curr->right) {
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
}
// we are traversing up the tree from the left
else if (curr->left == prev) {
if (curr->right) {
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
}
// we are traversing up the tree from the right
else if (curr->right == prev) {
cout << curr->data << " ";
s.pop();
}
prev = curr;  // record previously traversed node
}
}``````

This solve in O(n) time and O(h) space, where h is the depth of the tree.

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

Pseudo code for Post Order Traversal without Recursion.....
Using Single Stack and single variable...

``````PostOrderWithIteration(root)
stack stc = empty
prev = null
stc.push(root)
while(!stc.empty()){
curr = stc.top()
if curr == NULL
stc.pop()
//reached at leaf Node
elseif curr->left == NULL && curr->right == NULL
print curr->data
stc.pop()
//left child is already visited so push right
elseif curr->left == prev
stc.push(curr->right)
//left & right both child visited so print value
elseif curr->right == prev
print curr->data
stc.pop()
else
stc.push(curr->left)
prev = curr``````

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

``````Nice Idea Aks, but ur code fails for some inputs .... I did some modifications to handle all cases

postOrderIterative(node *root)
{
node *prev=null, *elem;
push(root);
while(StackIsnotempty())
{
elem = getTop();

if(elem->left == NULL && elem->right == NULL)
{
print(elem);
pop();
prev=elem;
continue;
}

if(elem->left == prev)
{
if(elem->right == NULL)
{
print(elem);
pop();
prev = elem;
continue;
}
push(elem->right);
}
else if(elem->left != NULL)
{
push(elem->left);
}

if(elem->right == prev)
{
print(elem);
pop();
prev=elem;
}

}
}``````

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

This link is also very helpful, for Pre/In/Post order iterative solutions :
zerocredibility.wordpress.com/2010/11/16/iterative-tree-traversal/

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

to learn about post order binary tree traversal using iterative method watch this video
youtu.be/hv-mJUs5mvU

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

there is no need to put two stacks...

we can do it one stack itself....

what I have done is crated a struct forTraversal where I can mark whether I have visited the node's left or right child...

if left child is not visited then first visit left child and then right child and then print value of node..

``````#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *left;
struct node *right;
};

typedef struct node* Node;

struct forTraversal
{
Node node;
int vleft;
int vright;
};

Node newNode(int data)
{
Node temp = (Node)malloc(sizeof(Node));
temp->data = data;
temp->left = temp->right = NULL;

return temp;
}

void insert(Node *head , int data) //Passing address of node because its data is being editted
{

else
{
else
}

}

void iterativePostOrder(Node root, int noOfNodes)
{
if(root == NULL)
return;

struct forTraversal *stack = (struct forTraversal *)malloc(sizeof(struct forTraversal)*noOfNodes);

int i=0;

for(i=0;i<noOfNodes;i++)
stack[i].vleft = stack[i].vright = 0;

int top = -1;

stack[++top].node = root;

while(top!=-1)
{
if(root->left != NULL && stack[top].vleft == 0)
{
stack[top].vleft = 1;
stack[++top].node = root->left;
root = root->left;
continue;
}

if(root->right!=NULL && stack[top].vright == 0)
{
stack[top].vright = 1;
stack[++top].node = root->right;
root = root->right;
continue;
}

printf("\n%d" , root->data);

stack[top].vleft = stack[top].vright = 0;

root = stack[--top].node;
}

}

int main()
{

printf("\nIterative Post order \n");

return 0;
}``````

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

use two stack

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

``````void postorder(TreeNode currentnode)
{
int top=-1;
Stack stack=new Stack(250);

while(true)
{
while(currentnode!=null)
{
top++;
stack.push(currentnode);
if(currentnode.right!=null)
{
currentnode.right.element = -(Integer)(currentnode.right.element);
top++;
stack.push(currentnode.right);
}
currentnode=currentnode.left;
}
if(top!=-1)
{
currentnode=(TreeNode)stack.pop();

while((Integer)(currentnode.element) >0 && top!=-1 )
{
System.out.printf("%d,",currentnode.element);
top--;
currentnode=(TreeNode)stack.pop();
}
if((Integer)(currentnode.element)<0 )
{
currentnode.element = - (Integer)currentnode.element;
top--;
}
if(top==-1)
{
break;
}
}
else
break;
}
System.out.printf("\b ");
}``````

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

My code uses a single stack but there is a trick where we mark the node's right child's element as negative and then push onto stack. This way we can avoid using 2 stacks.

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

Ok, I wrote some pseudo code for this problem, i think it should work.

pseudo code:

T.root is the root of the BST
create stack S1

push T.root into S1
while S1 is not empty
{
t1=pop( S1)

if t1.left==t1.right==NULL
print t1

else if t1.left !=NULL
t2=t1.left
t1.left==NULL
push(S1, t1)
push(S1, t1.left)

else
t2=t1.right
t1.right=NULL
push(S1, t1)
push(S1, t1.right)
}

Only draw back is you destroy your tree pointers in the process :P

probably make a copy of the tree and do the above algo.

running time O(n) where n is number of elements in the tree.
Reason:
each action inside the while loop runs in O(1) time,
and the loop runs n times.

For re-creating the tree, we could do this:

everytime we print an element, push it into another stack.
At the end use this 2nd stack to re-create our originial tree..
again, this can be done in O(n).

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

So we still have it running in O(n) time..

Actually, to be more specific its theta(n) time.

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

here is some pseudo code using a single stack. it uses a variable "f" to hold the status of the node to which pointer "p" is pointing.
f=0 =>node was just pushed into the stack proceed with the left child now.
f=1 =>left tree traversed. proceed with the right child.
f=2 =>both subtrees traversed. print the node's info and pop it out of the stack.
1. push(root), p=root,f=0;

``````while(stack not empty)
{
if(f==1)
{
if(p->right)
{
p=p->right;
push(p);
f=0;
}
else
f=2;
}
if(f==2)
{
print p->info;
top--;

if(stack[top]->right==p)
f=2;
else
f=1;

p=stack[top];
}
if(f==0)
{
if(p->left)
{
p=p->left;
push(p);
}
else
f=1;
}
}``````

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

``````public void inorder_recursive() {
inorder_recursiveT(root);
System.out.println();
}

private void inorder_recursiveT(TreeNode node) {
Stack<TreeNode> stack = new Stack<TreeNode>();
if (node == null) {
return;
}
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
curr = stack.peek();
stack.pop();
System.out.print(curr.element + " ");
curr = curr.right;
}
}
}``````

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

``````public void postorder_recursive() {
postorder_recursiveT(root);
}

private void postorder_recursiveT(TreeNode node) {
if (node == null) {
return;
}
TreeNode prev = null;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(node);
while (!stack.isEmpty()) {
TreeNode curr = stack.peek();
if (prev == null || prev.left == curr || prev.right == curr) {
if (curr.left != null) {
// left child is not null
stack.push(curr.left);
} else if (curr.right != null) {
// right child is not null
stack.push(curr.right);
} else {
// leaf
System.out.print(curr.element + " ");
stack.pop();
}
} else if (prev == curr.left) {
// traverse up from left child
if (curr.right != null) {
stack.push(curr.right);
} else {
System.out.print(curr.element + " ");
stack.pop();
}
} else if (prev == curr.right) {
// traverse up from right child
System.out.print(curr.element + " ");
stack.pop();
}
prev = curr;
}

}``````

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.