Pre-order-traversal non recursive

Here's a non recursive algorithm to implement preorder traversal of binary tree.

Note: When we say push a node on stack,it will mean push pointer to that node on stack i.e address of that node on stack.

Idea 

First we push the root in stack and then the right subtree and lastly the left subtree.

Algorithm

1.Initialize a stack variable. 

2.Push root node on stack.

3.Till stack is not empty

    i)Pop node from stack.Print it and make it as current node.

   ii)if right child exists for current node push it on stack. 

  iii)if left child exists for current node push it on stack.

Code

Lets try to implement the above algorithm by the below preorder function.

void preorder(node* root)
{
    node* curr;
    push(root);

    while(!empty())
    {
        curr=pop();
        printf("%c",curr->key);
        if(curr->right!=NULL)
            push(curr->right);
        if(curr->left!=NULL)
            push(curr->left);
    }
}

Code Tracing