InorderTreeGenerator.cpp

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {}
};

struct InorderTraverser {
    stack<TreeNode*> stk;
    TreeNode *x = nullptr;
    bool first = true;

    InorderTraverser(TreeNode *n) {
        while (n) {
            stk.push(n);
            n = n->left;
        }
    }

    TreeNode *operator()() {
        if (!first) {
            if (!x) return nullptr;
            goto cx;
        }
        first = false;
        while (!stk.empty()) {
            x = stk.top();
            stk.pop();
            // visit node 'x';
            return x; // yield the next node.
            cx: // resume execution from here.
            if (x->right) {
                stk.push(x->right);
                x = x->right;
                while (x->left) {
                    stk.push(x->left);
                    x = x->left;
                }
            }
        }
        return nullptr;
    }
};

int main() {
    TreeNode n1(100);
    TreeNode n2(50);
    TreeNode n3(150);
    TreeNode n4(20);
    TreeNode n5(60);
    TreeNode n6(170);
    TreeNode n7(160);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.right = &n6;
    n6.left = &n7;

    InorderTraverser t(&n1);    
    TreeNode *n = t();
    while (n) {
    	cout << n->val << ", ";
    	n = t();
    }
}