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

\

2Output:[3,1,null,null,2]

3

/

1

\

2

**Example 2:**

Input:[3,1,4,null,null,2]

3

/ \

1 4

/

2Output:[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; } }