Pre-Order Traversal

Because the characteristic of preorder traversal is to access the root node first, and then access the left and right subtrees, so the root node must be pushed into the stack first, then the root node of the right subtree is pushed in the stack, and then the root node of the left subtree is pushed into the stack, and then you can pop the stack and access it recursively. The basic idea is to use the last-in-first-out feature of the stack.

void PreOrder(Node* root)
{
    stack<Node*> stk;    
    Node* p = NULL;
    stk.push(root);
    while (stk.size())
    {
        p = stk.top();
        Visit(p);
        stk.pop(); 
        if (p->right) stk.push(p->right);
 
        if (p->left) stk.push(p->left);
    }
}

In-Order Traversal

In the inorder traversal, we recursively traverse the left subtree, visit the root node, and then traverse the right subtree.
The most common use case is binary search tree.

void Inorder(struct Node* node)
{
    Inorder(node->left);
    Visit(node);
    Inorder(node->right);
}

The algorithm above is easy but has no performance, now let’s consider traverse the tree without recursion in a single while.
The idea is: we first push the root in a stack, then check the top of the stack to see if it does not have left child or
it’s subtree has been traversed, if so we visit and pop it from the stack, and then continue to analyze its right subtree.

void InOrderIterative(Node* root)
{
    stack<Node*> stk;
    stk.push(root);
    Node* p = NULL;
    while (stk.size())
    {
        if (!stk.top()->left || p)
        {           
            p = stk.top();
            Visit(p);
            stk.pop(); 
            if (p->right)
            {
                stk.push(p->right); 
                p = NULL;
            }         
        }
        else
        {
            stk.push(stk.top()->left);          
        }
    }
}

Post-Order Traversal

For postorder traversal, we visit the entire left subtree, then the entire right subtree, and then the root node.
This means that the root node should be pushed in stack first so it can be the last node we can visit in the stack.

void PostOrderIterative(Node* root) 
{
    stack<Node*> stk;
    stk.push(root);
    Node *p = NULL, *L = NULL, *R = NULL;
    while (stk.size())
    {
        L = stk.top()->left;
        R = stk.top()->right;
        if (!L && !R || R && p == R || !R && p == L) 
        {
            p = stk.top();
            stk.pop();
            Visit(p);
        }
        else
        {
            if (R) stk.push(R);
 
            if (L) stk.push(L);
        }
    }
}

M-ary tree

The algorithm for a binary tree can be generalized into a m-ary tree (a tree where each node have no more than m children nodes).
The postorder algorithm for m-ary tree is:

    Traverse the subtrees.
    Visit the root node.