# An easy iteration solution works if no duplicate values in the tree

• I got passed a neatly designed iteration solution that is borrowed from another post. It pushes each node two times into the stack. When we pop up a node with same value as the next node in the stack, it is going down the tree. Otherwise, it is going up. I see that this method will fail if some duplicate values exist on the tree. However, it passed around the OJ tests. I guess there is not any such special case in the tests. For example: {2, 2, #, 2, #, #, #}. Anyway, it is good to know such a solution there.

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
stack<TreeNode *> s;
if (!root) return res;
s.push(root);
s.push(root);
while (!s.empty()) {
TreeNode * cur = s.top();
s.pop();
if (!s.empty() && cur->val == s.top()->val) {
if (cur->right) s.push(cur->right), s.push(cur->right);
if (cur->left) s.push(cur->left), s.push(cur->left);
}
else
res.push_back(cur->val);
}
return res;
}
};``````

• very good idea, and if we change

if (!s.empty() && cur->val == s.top()->val)

to

if (!s.empty() && cur == s.top())

i think this will solve duplicate values cases

• You are awesome! I think it works since the pointers are unique to each node.

• Would it fail if the leaf node has left = NULL and right = NULL?

• The key is to trace whether a node has been expanded. I use an extra variable to do this.
The observation is that if a node has been expanded, then the most recently popped node must be its left or right child. This voids doubling the stack.

Here is my code.

`````` public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode pre = null;  // track the most recently popped node
while(!stack.empty()){
TreeNode n = stack.peek();
if(n.left == null && n.right == null){
pre = n;
stack.pop();
continue;
}
if(pre != null && (n.left == pre || n.right == pre)){
pre = n;
stack.pop();
}
else{
if(n.right != null) stack.push(n.right);
if(n.left != null) stack.push(n.left);
}
}
return res;
}
``````

• The leaf node is supposed to have two NULL children. So I am not sure I get your point.

``````public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode pre = null;  // track the most recently popped node
while(!stack.empty()){
TreeNode n = stack.peek();

// we print cur node when it is a leaf node, or pre is a child of cur node
if(n.left == null && n.right == null ||
pre != null &&
(n.left == pre || n.right == pre)){