# 99. Recover Binary Search Tree
### Description
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
### Constraints
### Approach
### Links
* [GeeksforGeeks](https://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/)
* [Leetcode](https://leetcode.com/problems/recover-binary-search-tree/)
* [ProgramCreek](https://www.programcreek.com/2014/05/leetcode-recover-binary-search-tree-java/)
* [YouTube](https://youtu.be/LR3K5XAWV5k)
### **Examples**
{% tabs %}
{% tab title="Example 1" %}
**Input:** \[1, 3, null, null, 2]
**Output:** \[3, 1, null, null, 2]
{% endtab %}
{% tab title="Example 2" %}
Input: \[3, 1, 4, null, null, 2]
Output: \[2, 1, 4, null, null, 3]
{% endtab %}
{% endtabs %}
### **Solutions**
{% tabs %}
{% tab title="TreeNode" %}
```java
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
```
{% endtab %}
{% tab title="Solution 1" %}
```java
/**
* Time complexity : O(1) in the best case, and O(N) in the worst case when
* one of the swapped nodes is a rightmost leaf.
* Space complexity : up to O(H) to keep the recursion stack,
* where H is a tree height.
*/
class Solution {
private TreeNode first, last, prev;
public void recoverTree(TreeNode root) {
if(root == null) return;
findFaultyNodes(root);
if(first != null && last != null) {
int val = first.val;
first.val = last.val;
last.val = val;
}
}
// Basically inorder traversal
private void findFaultyNodes(TreeNode root) {
if(root == null) return;
findFaultyNodes(root.left);
if(prev == null) {
prev = root;
} else {
if(prev.val > root.val) {
if(first == null) {
first = prev;
}
last = root;
}
prev = root;
}
findFaultyNodes(root.right);
}
}
```
{% endtab %}
{% tab title="Solution 2" %}
```java
/**
* Time complexity : O(1) in the best case, and O(N) in the worst case when
* one of the swapped nodes is a rightmost leaf.
* Space complexity : up to O(H) to keep the recursion stack,
* where H is a tree height.
*/
class Solution {
public void recoverTree(TreeNode root) {
if(root == null) return;
TreeNode first = null, last = null, prev = null;
Deque stack = new ArrayDeque();
while(!stack.isEmpty() || root != null) {
while(root != null) {
stack.add(root);
root = root.left;
}
root = stack.removeLast();
if(prev != null && prev.val > root.val) {
last = root;
if(first == null) {
first = prev;
} else {
break;
}
}
prev = root;
root = root.right;
}
if(first != null && last != null) {
int val = first.val;
first.val = last.val;
last.val = val;
}
}
}
```
{% endtab %}
{% endtabs %}
### **Follow up**
* A solution using O(*n*) space is pretty straight forward.
* Could you devise a constant space solution?
