# C++ 10-12 lines iterative solution for Postorder, Preorder and Inorder traversal

• Big idea is to use a stack to record nodes to be processed.

Postorder:
Keep track of last processed node to indicate if current node is ready to be processed.

``````vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if (root) { st.push(root); }

// ensure last won't match root's left/right children
for (TreeNode *last = root, *cur; st.size() && (cur = st.top());) {
if ((!cur->left && !cur->right) || (cur->left == last && !cur->right) || (cur->right == last)) {
ans.push_back((last = cur)->val); st.pop();     // it's cur's turn to get recorded
} else {
if (cur->right) { st.push(cur->right); }
if (cur->left) { st.push(cur->left); }
}
}

return ans;
}
``````

Preorder:

``````vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if (root) { st.push(root); }

while (st.size()) {
TreeNode* cur = st.top(); st.pop();             // process current node
ans.push_back(cur->val);                        // record node value
if (cur->right) { st.push(cur->right); }
if (cur->left) { st.push(cur->left); }
}

return ans;
}
``````

Inorder:
Always put leftmost node to process on top of the stack.

``````class Solution {
private:
stack<TreeNode*> st;

void update(TreeNode* cur) {
for (; cur; cur = cur->left) {
st.push(cur);                               // pushing left node into stack all the way
}
}

public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
update(root);                                   // add root in stack

for (TreeNode* cur; st.size() && (cur = st.top()); st.pop(), update(cur->right)) {
ans.push_back(cur->val);                    // record leftmost value and add candidate right node in stack
}

return ans;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.