// Iterative way (not constant space then)

```
public void recoverTree(TreeNode root) {
Stack<TreeNode> stk = new Stack<TreeNode>();
TreeNode first = null;
TreeNode second = null;
int last = Integer.MIN_VALUE;
//iterative way to inorder traverse a tree
while (root != null || !stk.empty()) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
if (first == null) {
last = root.val;
first = root;
}
else {
if (last < root.val) {
last = root.val;
if (second == null)
first = root;
}
else {
if (second == null) {
second = root;
last = root.val;
}
else {
last = root.val;
root.val = first.val;
first.val = last;
return;
}
}
}
root = root.right;
}
// case : 3->2->4->5 will go through here with first = 3 second = 2
if (first == null || second == null)
return;
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
```

Recursive way with constant space:

```
public void recoverTree(TreeNode root) {
helper(root);
if(!done){
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
}
private TreeNode first = null;
private TreeNode second = null;
private int last = Integer.MIN_VALUE;
private boolean refer = false;
private boolean done = false;
private void helper(TreeNode root) {
if (root == null)
return;
helper(root.left);
if (first == null) {
last = root.val;
first = root;
}
else {
if (last < root.val) {
//System.out.println(last+"|"+root.val);
last = root.val;
if (!refer)
first = root;
}
else {
if (!refer){
refer = true;
second = root;
last = root.val;
}
else {
last = root.val;
root.val = first.val;
first.val = last;
done = true;
}
}
}
helper(root.right);
}
```