non recursive post order traversal of a binary tree

postorder.cpp

//  Created by Steve Myers on 11/22/14.

#include <iostream>
#include <stack>
#include <stdexcept>
#include <array>
#include "binarySearchTree.h"

using namespace std;

template<typename T>
class binaryTreeNonRec : public bSearchTreeType<T>
{
    const static int NONE_VISITED = 0;
    
    const static int LEFT_VISITED = 1;
    const static int RIGHT_VISISTED = 2;
    
    struct postOrderHelper {
        binaryTreeNode<T>* node;
        int state;
        
        postOrderHelper(binaryTreeNode<T>* node, int state) :
                                                node { node }, state { state }
        {
            if (state != LEFT_VISITED && state != RIGHT_VISISTED)
                throw invalid_argument { "Not a valid state" };
        }
    };
    
public:
    
    template<typename Func>
    void nonRecursivePostTraversal(Func func) const
    {
        stack<postOrderHelper> stack;
        binaryTreeNode<T>* current = this->root;
        int state = NONE_VISITED;
        
        if (current == nullptr) return;
        
        stack.push(postOrderHelper { current, LEFT_VISITED });
        
        current = current->llink;
        
        while (!stack.empty())
        {
            if (current != nullptr && state == NONE_VISITED)
            {
                stack.push(postOrderHelper { current, LEFT_VISITED });
                current = current->llink;
            }
            else
            {
                current = stack.top().node;
                state = stack.top().state;
                stack.pop();
                
                if (state == LEFT_VISITED)
                {
                    stack.push(postOrderHelper { current, RIGHT_VISISTED });
                    current = current->rlink;
                    state = NONE_VISITED;
                }
                else
                {
                    func(current->info);
                }
            }
        }
        
    }
};


int main() {
    const array<int, 10> testItems { 1, 10, 34, 56, 23, 11, 4, 15, 22, 78 };
    
    binaryTreeNonRec<int> tree;
    for (const auto& item : testItems) tree.insert(item);
    
    tree.postorderTraversal();
    cout << endl;
    
    tree.nonRecursivePostTraversal([](int m) { cout << m << " "; });
    
//  OUTPUTS:
//    4 22 15 11 23 78 56 34 10 1
//    4 22 15 11 23 78 56 34 10 1

    return 0;
}