I've solved it using a stack and a hash map to keep track of already visited nodes so that I don't process them again and again. But it'd be nice to solve without the hash map so that I don't need O(n) space, Here's my code. Thanks

{

```
map<TreeNode*,bool> seenMap;
stack<TreeNode*> s;
vector<int> result;
TreeNode* curr = root;
if (root)
s.push(root);
while (!s.empty())
{
if (curr->left && (seenMap.find(curr->left) == seenMap.end()))
{
curr = curr->left;
s.push(curr);
continue;
}
else
{
curr = s.top();
s.pop();
result.push_back(curr->val);
seenMap[curr] = true;
}
if (curr->right && (seenMap.find(curr->right) == seenMap.end()))
{
curr = curr->right;
s.push(curr);
}
}
return result;
```

}