Tree Traversals

Write functions (both iterative and recursive)for the following binary tree traversals

http://algorithms.tutorialhorizon.com/tree-traversals/

   i)Inorder---USING 1)Recursion 2)Stack 3)Without using Stack or Recursion---Morris Traversal
  ii)Preorder
 iii)Postorder

Traversal Visualisation:
http://nova.umuc.edu/~jarc/idsv/lesson1.html

Difference between iterative pre and in ----
Inorder:Push->Pop->process->go to right--Process the node after popping[after completion of left subtree processing

Preorder:Process->Push->Pop ->go to right---Process Current node and and before going to left subtree store the current in stack

Inorder_iteartive
http://algorithms.tutorialhorizon.com/inorder-traversal-non-recursive-approach/
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current 

is NULL
4) If current is NULL and stack is not empty then
     a) Pop the top item from stack.
     b) Print the popped item, set current = current->right
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

Usage:

1. Merge 2 unbalanced BSTs

http://www.geeksforgeeks.org/merge-two-bsts-with-limited-extra-space/

Preorder_Iterative:
http://algorithms.tutorialhorizon.com/binary-tree-preorder-traversal-non-recursive-approach/
http://www.geeksforgeeks.org/iterative-preorder-traversal/
1.Push the address of root node onto the stack
2.Pop an address from the stack
3.If the popped address is not NULL
     Traverse the node
     Push right child of node on stack
     Push left child of node on stack
4.Repeat steps 2 & 3 until the stack is not empty

Postorder Iterative:

Method 1:Using flag array 

1) Create an empty stack S and push NULL on stack
2) Repeat steps 3,4,5 while current!=NULL
3) Move on the leftmost path rooted at current and all nodes which come 
on this path are to be pushed on stack and the value of flag is made 1 
for these nodes.We also push right child of of current nodes to the stack
and make the value of flag -1 for these nodes.
4) Save the value of top in top_prev and pop an address from tha stack 
and assign to current
5)Repeat the following steps while flag[top_prev]==1
i)Traverse the node whose address is current
ii)Pop another node from the stack
 
As soon as we get the value flag[top_prev] as -1 we move to step 3 because
we have got a right subtree of a node which again has to be traversed in 
postorder.

Method 2 :Using  Two stacks 

http://algorithms.tutorialhorizon.com/binary-tree-postorder-traversal-non-recursive-approach/

http://www.geeksforgeeks.org/iterative-postorder-traversal/

http://articles.leetcode.com/binary-tree-post-order-traversal

 This basic logic behind this is doing a reversed pre-order traversal.
 That is, the order of traversal is a node,then its right child followed by its left child. 
 This yields post-order traversal in reversed order. Using a second stack, we could reverse it
 back to the correct order.

• Push the root node to the child stack.
• while child stack is not empty
• Pop a node from the child stack, and push it to the parent stack.
• Push its left child followed by its right child to the child stack.
• end while
• Now the parent stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the parent stack one by one and you will have the post order traversal of the tree.

Method 3:Using Single Stack & Storing previous Node 

http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

http://www.leetcode.com/2010/10/binary-tree-post-order-traversal.html

Code:

#include<stdio.h>
#include<stdlib.h>
#define bool int
struct tree
{
   int data;
   struct tree* left;
   struct tree* right;
};
struct List
{
  struct tree *t;
  struct List *next;
};

void push(struct List*& head, struct tree *t)
{
  struct List* new_tree =
            (struct List*) malloc(sizeof(struct List));

  if(new_tree == NULL)
  {
     printf("Stack Overflow \n");
     getchar();
     exit(0);
  }         
  new_tree->t  = t;
  new_tree->next = head;
  head    = new_tree;
}

bool isEmpty(struct List *top)
{
   return (top == NULL)? 1 : 0;
}

struct tree *pop(struct List*& head)
{
  struct tree *res;
  struct List *top;
  if(isEmpty(head))
  {
     printf("Stack Underflow \n"); //Return NULL for Postorder
     getchar();
     exit(0);
  }
  else
  {
     top = head;
     res = top->t;
     head = top->next;
     free(top);
     return res;
  }
}
 void inOrder(struct tree *root)
{
  struct tree *current = root;
  struct List *s = NULL;
  bool done = 0;

  while (!done)
  {
    if(current !=  NULL)
    {
      push(s, current);
      current = current->left;
    }
    else
    {
      if (!isEmpty(s))
      {
        current = pop(s);
        printf("%d ", current->data);
        current = current->right;
      }
      else
        done = 1;
    }
  }
}

void preOrder(struct tree *root)
{ struct tree *current = root;
  struct List *s = NULL;
 
  push(s,current);
  while(!isEmpty(s))
     {  current = pop(s);
     if(current!=NULL)
       { printf("%d ", current->data);
        push(s,current->right);
        push(s,current->left);
        }
     } 
  }

void postOrder(struct tree *root)
{
int flag[100];int top_prev;int top=0;

struct tree *current = root;
struct List *s = NULL;

  do{
         while(current!=NULL)
         {
             push(s,current);
             flag[++top]=1;
             if(current->right!=NULL)
             {   push(s,current->right);
                 flag[++top]=-1;
             }
             current=current->left;
         }

         top_prev=top;
         current=pop(s);
         --top;
         while(flag[top_prev]==1)
          {
             printf("%d\n",current->data);
             top_prev=top;
             current=pop(s);
             --top;    
           }

    }while(current!=NULL);
   
}      
  
struct tree* newtree(int data)
{
  struct tree* tree = (struct tree*)
                       malloc(sizeof(struct tree));
  tree->data = data;
  tree->left = NULL;
  tree->right = NULL;
  return(tree);
}

int main()
{
  struct tree *root = newtree(1);
  root->left        = newtree(2);
  root->right       = newtree(3);
  root->left->left  = newtree(4);
  root->left->right = newtree(5);

  inOrder(root);

  getchar();
  return 0;
}
Time Complexity: O(n)