//   1

//  /  \

//  2  3

// /  \    \

// 4  5     6

struct TreeNode {

    int val;

    TreeNode* left;

    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};

void inorderIterative(TreeNode* root) {

    stack<TreeNode*> st;

    TreeNode* curr = root;

    while (curr || !st.empty()) {

       while (curr) {

           st.push(curr);

           curr = curr->left;

       }

       curr = st.top(); st.pop();

       cout << curr->val << " ";

       curr = curr->right;

    }

}