# Leetcode 99 – Recover Binary Search Tree – Constant space

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure with constant space.

Example 1:

`Input: [1,3,null,null,2]       1    /  3    \      2 Output: [3,1,null,null,2]      3    /  1    \      2`

Example 2:

`Input: [3,1,4,null,null,2]     3   / \ 1   4       /     2 Output: [2,1,4,null,null,3]     2   / \ 1   4       /     3`

A solution using O(n) space is pretty straight forward using stack. but we need to achieve it with constant space.

Also we know that in-order traversal of BST is sorted output. So while doing in-order traversal, we should find 2 nodes, which need to be swapped to get the sorted output.

```public void RecoverTree(TreeNode root) {
TreeNode prev = null;
TreeNode first = null, next = null;

TreeNode current = root;
while (current != null)
{
if (prev != null && current != null && prev.val > current.val)
{
if (first == null)
{
first = prev;
next = current;
}
else
{
next = current;
}
}

//left is null then print the node and go to right
if (current.left == null)
{
//update previous pointer
prev = current;

Console.Write(current.val + " ");
current = current.right;
}
else
{
//find the predecessor.
TreeNode predecessor = current.left;
//To find predecessor keep going right till right node is not null or right node is not current.
while (predecessor.right != current && predecessor.right != null)
{
predecessor = predecessor.right;
}

//if right node is null then go left after establishing link from predecessor to current.
if (predecessor.right == null)
{
predecessor.right = current;
current = current.left;
}
else
{
//left is already visit. Go rigth after visiting current.
predecessor.right = null;
Console.Write(current.val + " ");

//update previous pointer
prev = current;

current = current.right;
}
}
}

//Swap values
if(first!=null && next !=null)
{
int temp = first.val;
first.val = next.val;
next.val = temp;
}
}
```