# Cause of Infinite Loop? (iterative inorder traversal implementation) C++

Question: Implement Inorder Traversal iteratively.

My Attempt: (results in an infinite loop that I haven't been able to debug) any help or suggestions greatly appreciated

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
#include <vector>
#include <stack>
#include <unordered_set>
using namespace std;

class Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

//iterative sol:
vector<int> sol;
stack<TreeNode*> dfs;
dfs.push(root);
unordered_set<TreeNode*> visited;
visited.insert({root});
TreeNode* temp;

while (!dfs.empty()) {

if (dfs.top()->left != nullptr && visited.find(dfs.top()->left) == visited.end()) {
dfs.push(dfs.top()->left);
visited.insert({dfs.top()->left});
}
else {
sol.push_back(dfs.top()->val);
temp = dfs.top();
dfs.pop();

if (temp->right != nullptr && visited.find(temp->right) == visited.end()) {
dfs.push(temp->right);
visited.insert({temp->right});
}
}

}

return sol;

}
};
``````

EDIT: I don't have the specific internal definitions of the TreeNode, but if you want to run the problem, checkout: https://leetcode.com/problems/binary-tree-inorder-traversal/

Here is the problem :

``````dfs.push(dfs.top()->left);
visited.insert(dfs.top()->left);
``````

You are pushing to stack (then `dfs.top()` will change) and then accessing `dfs.top()->left` in the next line.

It only takes 2 simple rules to implement an iterative in-order traversal.

If you're at node X, then:

1. If X has a right child, then move to the right child, and follow as many left links as possible to find the next node.
2. Otherwise, find the closest ancestor of X on the right, i.e., the closest ancestor whose left subtree contains X. If there is no such ancestor then you're done.

If your tree doesn't have parent links, then you'll need a stack to store the right ancestors, but there's no need for a visited set:

``````vector<int> inorderTraversal(TreeNode* tree) {
vector<int> ret;
stack<TreeNode *> nextParents;
for(;tree; tree = tree.left) {
nextParents.push(tree);
}
while(!nextParents.empty()) {
tree = nextParents.pop();
ret.push_back(tree->val);
for(tree = tree.right; tree; tree = tree.left) {
nextParents.push(tree);
}
}
return ret;
}
``````

You are modifying the stack in the first line here

``````  dfs.push(dfs.top()->left);
visited.insert({dfs.top()->left});
``````

what you want to do is to mark the previous `dfs.top()->left` as visited, but you are adding more element on top of the stack and thus the new `dfs.top()` is a different one.

To solve this problem you should use store the previous `dfs.top()->left` in a different variable.

As a best practice, the variable or object you are working on should be immutable, since the stack is not immutable don't use its `top` while inserting into it or doing some other computations. Instead store your required variable into something immutatble like `temp` here

`````` temp = dfs.top();
if (temp->left != nullptr && visited.find(temp->left) == visited.end()) {
dfs.push(temp->left);
visited.insert({temp->left});
}
else {
sol.push_back(dfs.top()->val);
dfs.pop();

if (temp->right != nullptr && visited.find(temp->right) == visited.end()) {
dfs.push(temp->right);
visited.insert({temp->right});
}
}
``````