# Iterative method to do three kinds of traversal just like recursive method only changing one line code

• For three different kinds of traversal, we only need to change the order of tuples in one line as we've done this in the recursive solution which is very decent and classical. Just put `(0, p[1])` in different position!

For post-order traversal:

``````def postorderTraversal(self, root):
res, stack = [], [(1, root)]
while stack:
p = stack.pop()
if not p[1]: continue
stack.extend([(0, p[1]), (1, p[1].right), (1, p[1].left)]) if p[0] != 0 else res.append(p[1].val)
return res
``````

For in-order traversal:

``````def inorderTraversal(self, root):
res, stack = [], [(1, root)]
while stack:
p = stack.pop()
if not p[1]: continue
stack.extend([(1, p[1].right), (0, p[1]), (1, p[1].left)]) if p[0] != 0 else res.append(p[1].val)
return res
``````

For pre-order traversal:

``````def preorderTraversal(self, root):
res, stack = [], [(1, root)]
while stack:
p = stack.pop()
if not p[1]: continue
stack.extend([(1, p[1].right), (1, p[1].left), (0, p[1])]) if p[0] != 0 else res.append(p[1].val)
return res``````

• Hah, nobody cares this solution... I think it's super easy to write when you face it in a interview. Just change the order in `[(), (), ()]`

• @jedihy
The solution is so elegant! Why nobody gives thumbs up for it.

• Excellent solution, have learned a lot from your post!!

• Can someone please rewrite this into c++? Not familiar with python... Thanks!

• Here is my solution, using recursive + iterative + morris
leetcode 145

• @jedihy could you explain a little about this code? thanks

• Here's the same idea in C++:

``````enum { ENTER, EXIT };

class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<pair<int, TreeNode*>> s;
s.push(make_pair(ENTER, root));
while (s.size() > 0) {
pair<int, TreeNode*> event = s.top();
s.pop();
TreeNode* node = event.second;
if (node == nullptr) continue;

if (event.first == EXIT) {
ans.push_back(node->val);
} else {
s.push(make_pair(EXIT, node));
s.push(make_pair(ENTER, node->right));
s.push(make_pair(ENTER, node->left));
}
}
return ans;
}
};
``````

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