/*
Non-Recursive Binary Tree Traversal Algorithms

These are several algorithms I had trouble with.  They
are written in standard C++ and use data structures from
the STL.  The special headers for them are included for
convenience.  The source was translated to HTML with the
excellent open source text editor gvim.
*/

#include <stack>

void preorderTraversal(Node* const v)
{
    if(v != NULL)
    {
        stack<Node*> s;
        Node* tmp = 0;
        
        tmp = v;
        s.push(tmp);
        
        while(!s.empty())
        {
            tmp = s.top();
            s.pop();
            
            if(tmp != NULL)
            {
                visit(tmp);
                s.push(tmp->right);
                s.push(tmp->left);
            }
        }
    }
}

#include <stack>

void inorderTraversal(Node* const v)
{
    if(v != NULL)
    {
        stack<Node*> s;
        Node* tmp = 0;
        
        tmp = v;
        
        while(tmp->left)
            tmp = tmp->left;
        s.push(tmp);
        
        while(!s.empty())
        {
            tmp = s.top();
            s.pop();
            
            visit(tmp);

            if(tmp->right)
            {
                tmp = tmp->right;
                s.push(tmp);

                while(tmp->left)
                    tmp = tmp->left;
                s.push(tmp);
            }
        }
    }
}

#include <queue>

void levelTraversal(Node* const v)
{
    if(v != NULL)
    {
        queue<Node*> q;
        Node* tmp = 0;
        
        tmp = v;
        q.push(tmp);
        
        while(!q.empty())
        {
            tmp = q.front();
            q.pop();
            
            if(tmp != NULL)
            {
                visit(tmp);
                q.push(tmp->left);
                q.push(tmp->right);
            }
        }
    }
}