Microsoft Interview Question
Country: India
Interview Type: In-Person
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.
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.
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
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;
}
}
}
This link is also very helpful, for Pre/In/Post order iterative solutions :
zerocredibility.wordpress.com/2010/11/16/iterative-tree-traversal/
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
{
if(*head == NULL)
*head= newNode(data);
else
{
if(data <= (*head)->data)
insert(&((*head)->left),data);
else
insert(&((*head)->right),data);
}
}
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()
{
Node head = NULL;
insert(&head,4);
insert(&head,3);
insert(&head,6);
insert(&head,5);
insert(&head,7);
insert(&head,8);
insert(&head,1);
printf("\nIterative Post order \n");
iterativePostOrder(head,7);
return 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 ");
}
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).
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;
}
}
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;
}
}
}
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;
}
}
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
- Anonymous July 09, 2012youtu.be/hv-mJUs5mvU