#include <iostream>
#include <vector>
#include <stack>


using namespace std;

typedef struct Node {
    int data;
    struct Node* lchild;
    struct Node* rchild;

    Node(int val) {
        this->data = val;
        this->lchild = this->rchild = NULL;
    }
}Node;

void visit(Node* item) {
    if (item) {
        cout << "val:" << item->data << endl;
    }
}

void travel(Node* root) {
    if (root != NULL) {
        travel(root->lchild);
        travel(root->rchild);
        visit(root);
    }
}

void travel_inorder(Node* root) {
    if (root == NULL) {
        return;
    }
    Node* p = root;
    stack<Node*> s;
    while (!s.empty() || p) {
        while (p) {
            s.push(p);
            p = p->lchild;
        }
        if (!s.empty()) {
            p = s.top();
            s.pop();
            visit(p);
            p = p->rchild;
        }
    }
}

void test() {
    Node* root = new Node(-1);
    root->lchild = new Node(1);
    root->rchild = new Node(2);
    root->lchild->lchild = new Node(3);
    root->lchild->rchild = new Node(4);
    root->rchild->lchild = new Node(5);
    root->rchild->rchild = new Node(6);

    //travel(root);
    travel_inorder(root);
}

int main(int argc, char** argv) {
    test();
    return 0;
}