# 99. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

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.
• Could you devise a constant space solution?

Thoughts:

1. In-order traversal + first, sec, prev node global record
2. Morris traversal to save space

Code 1 T: O(n); S: O(n) due to call stack space:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode first;
TreeNode sec;
TreeNode prev;
public void recoverTree(TreeNode root) {
if(root == null) return;
inorder_traversal(root);
// swap the first and sec value
int tmp = first.val;
first.val = sec.val;
sec.val = tmp;

return;
}
private void inorder_traversal(TreeNode cur){
if(cur == null) return;
inorder_traversal(cur.left);

if(first == null && (prev != null && prev.val > cur.val)) first = prev;
if(first != null && prev.val > cur.val) sec = cur;

prev = cur;
inorder_traversal(cur.right);

}
}
``````

Code 2: T:O(n); S: O(1)

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void recoverTree(TreeNode root) {
TreeNode prev = null; // previous node in in-order traversal
TreeNode first = null;
TreeNode sec = null;

// Morris Traversal:
TreeNode pred = null; // previous node in Morris Traversal
while(root != null){
if (root.left != null){
pred = root.left;
while(pred.right != null && pred.right != root){
pred = pred.right;
}

if(pred.right == null){
// connecting
pred.right = root;
root = root.left;
}
else{
// pred.right == root: visited
// record the first and second node
if(prev.val > root.val){
if(first == null) {first = prev; sec = root;}
else {sec = root;}
}

// disconnecting
pred.right = null;
// updating prev
prev = root;
root = root.right;

}
}
else{

if(prev != null && prev.val > root.val){
if(first == null) {first = prev; sec = root;}
else {sec = root;}
}

prev = root;
root = root.right;
}
}
// swap first and sec node values
// if(first != null && sec != null){
int tmp = first.val;
first.val = sec.val;
sec.val = tmp;
// }

}

}
``````