#include <iostream>
#include <stack>

using namespace std;

// abstract iterator interface
template <typename T>
class Iterator
{
public:
    virtual bool hasNext() = 0;
    virtual T next() = 0;
};

// binary tree implementation
class BinaryTree
{
private:
    struct TreeNode {
        int data;
        TreeNode *left, *right;

        TreeNode(int d = -1, TreeNode *l = nullptr, TreeNode *r = nullptr) :
            data(d), left(l), right(r) {}
    };

    TreeNode *root;

public:
    // preorder iterator
    class PreorderIterator : public Iterator<TreeNode*>
    {
    private:
        TreeNode *cur;
        stack<TreeNode*> s;

    public:
        PreorderIterator(TreeNode *root = nullptr) : cur(root)
        {
        }

        bool hasNext()
        {
            if (!cur && s.empty()) return false;

            TreeNode *tc = cur; // temp cur
            stack<TreeNode*> ts = s; // temp stack

            TreeNode *n = next();
            if (!n) return false;

            // restore cur and stack s
            cur = tc;
            swap(s, ts); // faster than s = ts;
            return true;
        }

        // might return nullptr
        // hasNext will use it to make a decision
        TreeNode* next()
        {
            TreeNode *ret = nullptr;
            if (!cur) {
                do {
                    cur = s.top();
                    s.pop();
                    cur = cur->right;
                } while (!cur && !s.empty());
            }

            if (cur) {
                s.push(cur);
                ret = cur;
                cur = cur->left;
            }
            return ret;
        }
    };

    // inorder iterator
    class InorderIterator : public Iterator<TreeNode*>
    {
    private:
        TreeNode *cur;
        stack<TreeNode*> s;

    public:
        InorderIterator(TreeNode *root = nullptr) : cur(root)
        {
        }

        bool hasNext()
        {
            if (!cur && s.empty()) return false;

            return true;
        }

        // never return nullptr
        TreeNode* next()
        {
            TreeNode *ret = nullptr;
            // guarantee no crash if hasNext() returns false, but still
            // try to call next()
            // if (!cur && s.empty()) return ret;

            if (!cur) {
                cur = s.top();
                s.pop();
                ret = cur;
                cur = cur->right;
                return ret;
            }

            while (cur && cur->left) {
                s.push(cur);
                cur = cur->left;
            }

            ret = cur;
            cur = cur->right;
            return ret;
        }
    };

    // postorder iterator
    class PostorderIterator : public Iterator<TreeNode*>
    {
    private:
        TreeNode *cur, *prev;
        stack<TreeNode*> s;

    public:
        PostorderIterator(TreeNode* root = nullptr) : cur(root), prev(nullptr)
        {
        }

        bool hasNext()
        {
            if (!cur && s.empty()) return false;

            return true;
        }

        // never return nullptr
        TreeNode* next()
        {
            TreeNode *ret = nullptr;
            // if (!cur && s.empty()) return ret;

            while (true) {
                while (cur) {
                    s.push(cur);
                    cur = cur->left;
                }

                cur = s.top();
                if (cur->right && cur->right != prev) {
                    cur = cur->right;
                    s.push(cur);
                    cur = cur->left;
                } else {
                    break;
                }
            }

            ret = cur;
            prev = cur;
            s.pop();
            cur = nullptr;
            return ret;
        }
    };

private:
    // create tree recursively with pre-order
    // s[i] == '#' means this tree is empty
    TreeNode* CreateTree(const string &s, int &idx)
    {
        if (s[idx] == '#') // null tree
            return nullptr;

        TreeNode *t = new TreeNode(s[idx]);
        t->left = CreateTree(s, ++idx);
        t->right = CreateTree(s, ++idx);
        return t;
    }

    void destroy(TreeNode *t)
    {
        if (!t) return;

        destroy(t->left);
        destroy(t->right);
        delete t;
    }

    void Init(const string &s)
    {
        int idx = 0;
        root = CreateTree(s, idx);
    }

public:

    BinaryTree(const string &s)
    {
        // please guarantee s is valid
        // do not check it here
        Init(s);
    }

    ~BinaryTree()
    {
        destroy(root);
    }

    void Handle(TreeNode *t)
    {
        cout << static_cast<char>(t->data) << "-->";
    }

    void PreOrder()
    {
        TreeNode *cur = root;
        stack<TreeNode*> s;

        while (cur || !s.empty()) {
            if (cur) {
                s.push(cur);
                Handle(cur);
                cur = cur->left;
            } else {
                cur = s.top();
                s.pop();
                cur = cur->right;
            }
        }
    }

    void InOrder()
    {
        TreeNode* cur = root;
        stack<TreeNode*> s;

        while (cur || !s.empty()) {
            if (cur) {
                s.push(cur);
                cur = cur->left;
            } else {
                cur = s.top();
                s.pop();
                Handle(cur);
                cur = cur->right;
            }
        }
    }

    void PostOrder()
    {
        TreeNode* cur = root, *prev = nullptr;
        stack<TreeNode*> s;

        while (cur || !s.empty()) {
            if (cur) {
                s.push(cur);
                cur = cur->left;
            } else {
                cur = s.top();

                if (cur->right && cur->right != prev) {
                    cur = cur->right;
                    s.push(cur);
                    cur = cur->left;
                } else {
                    s.pop();
                    Handle(cur);
                    prev = cur;
                    cur = nullptr;
                }
            }
        }
    }

    shared_ptr<PreorderIterator> CreatePreorderIterator()
    {
        return shared_ptr<PreorderIterator>(new PreorderIterator(root));
    }

    shared_ptr<InorderIterator> CreateInorderIterator()
    {
        return shared_ptr<InorderIterator>(new InorderIterator(root));
    }

    shared_ptr<PostorderIterator> CreatePostorderIterator()
    {
        return shared_ptr<PostorderIterator>(new PostorderIterator(root));
    }
};

int main(int argc, const char* argv[])
{
    /*
     *   Test  Tree
     *
                   A
                 /   \
                B     F
               / \    /
              C   D   G
                 /     \
                E       H
     */

    // preorder of tree node, # means empty subtree
    string s("ABC##DE###FG#H###");
    BinaryTree t(s);

    cout << "PreOrder: " << endl;
    t.PreOrder();
    cout << endl;
    auto pre = t.CreatePreorderIterator();
    while (pre->hasNext()) {
        t.Handle(pre->next());
    }
    cout << endl;

    cout << "InOrder: " << endl;
    t.InOrder();
    cout << endl;
    auto in = t.CreateInorderIterator();
    while (in->hasNext()) {
        t.Handle(in->next());
    }
    cout << endl;

    cout << "PostOrder: " << endl;
    t.PostOrder();
    cout << endl;
    auto post = t.CreatePostorderIterator();
    while (post->hasNext()) {
        t.Handle(post->next());
    }
    cout << endl;

    return 0;
}