# JAVA Recursive/Iterative Way with O(1) space and O(n) time

• // 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);
}``````

• you are using stack, obviously this is not constant space.

• My bad. Forgot that iterative way will always need space to store TreeNode.
New recursive way with constant space is attached

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