Traversal (inorder,preorder,postorder) of Binary Tree using recursion and also iteratively in c.

Hi friends,
      I will focus on how to traverse binary tree using iterative method which is tricky as compared to traversal using recursion. Consider following binary tree for example:

Inorder traversal means (left,visit,right) for every node starting from root .Inorder traversal for above tree gives:               1 3 4 6 7 8 10 13 14

Preorder traversal means (visit,left,right) for every node starting from root .Preorder traversal for above tree gives:               8 3 1 6 4 7 10 14 13

Postorder traversal means (left,right,visit) for every node starting from root .Postorder traversal for above tree gives:               1 4 7 6 3 13 14 10 8

Assume Node defination as:

typedef struct BinaryTreeNode
{
    int key;
    struct BinaryTreeNode *left,*right,*parent;
}TreeNode;

/*Recursive Inorder traversal: This traversal print keys in non-decreasing sorted order */

void traverse_inorder_rec(TreeNode *root)
{
    if(root!=NULL)
    {
        traverse_inorder_rec(root->left);
        printf("%d ",root->key);
        traverse_inorder_rec(root->right);
    }
}

/*Recursive Preorder traversal*/

void traverse_preorder_rec(TreeNode *root)
{
    if(root!=NULL)
    {
        printf("%d ",root->key);
        traverse_preorder_rec(root->left);
        traverse_preorder_rec(root->right);
    }
}

/*Recursive Postorder traversal: This traversal is helpful for deleting tree*/

void traverse_postorder_rec(TreeNode *root)
{
    if(root!=NULL)
    {
        traverse_postorder_rec(root->left);
        traverse_postorder_rec(root->right);
        printf("%d ",root->key);
    }
}

/*In all 3 iterative traversals we use stack as auxiliary data structure*/

/*Iterative Preorder: This is the most easiest among all 3 iterative traversals*/

void traverse_preorder_iterative(TreeNode *root)
{
    /*
    *Node's currently on stack are nodes whose keys are to be printed
    and left and right both child to be processed later.

    *All TreeNode * in stack are non NULL
    */
    stack<TreeNode *> s;
    if(root!=NULL)
    {
        s.push(root);
        while(!s.empty())
        {
            TreeNode *ptr=s.top();
            s.pop();
            printf("%d ",ptr->key);
            if(ptr->right!=NULL)
                s.push(ptr->right);
            if(ptr->left!=NULL)
                s.push(ptr->left);
        }
    }
}

/*Iterative Inorder traversal*/

void traverse_inorder_iterative(TreeNode *root)
{
        stack<TreeNode *> s;
        TreeNode *current=root;
        bool done =false;
        while(!done)
        {
            if(current)
            {
                s.push(current);
                current=current->left;
            }
            else
            {
                if(s.empty())
                {
                    done=true;
                }
                else
                {
                    current=s.top();
                    s.pop();
                    cout<<current->key<<" ";
                    current=current->right;
                }
            }
        }
}

/*Iterative post order traversal: This is the most trickiest among all this 3 iterative versions.Here we use prevNode pointer for keeping track in which direction we are moving.For eg. Either (upward from left or right ) or (downward from left or right )*/

void traverse_postorder_iterative(TreeNode *root)
{
    if(root!=NULL)
    {
        stack<TreeNode *> s;
        TreeNode *prevNode,*currentNode;
        prevNode=NULL;
        s.push(root);

        while(!s.empty())
        {
            currentNode=s.top();
            if(prevNode==NULL || prevNode->left==currentNode ||                            
                prevNode->right==currentNode)
            {
                if(currentNode->left!=NULL)
                    s.push(currentNode->left);
                else if(currentNode->right!=NULL)
                    s.push(currentNode->right);
                else
                {
                    printf("%d ",currentNode->key);
                    s.pop();
                }
            }
            else if(prevNode==currentNode->left)
            {
                if(currentNode->right!=NULL)
                    s.push(currentNode->right);
                else
                {
                    printf("%d ",currentNode->key);
                    s.pop();
                }
            }
            else if(prevNode==currentNode->right)
            {
                printf("%d ",currentNode->key);
                s.pop();
            }
            prevNode=currentNode;
        }
    }
}

Please comment if any doubt and like if helpful.

For detail explanation of postorder iterative version ,refer to link:http://leetcode.com/2010/10/binary-tree-post-order-traversal.html