> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/trees/bst/99.-recover-binary-search-tree.md).

# 99. Recover Binary Search Tree

## Problem Statement

<br>

You are given the `root` of a binary search tree (BST), where the values of **exactly** two nodes of the tree were swapped by mistake. *Recover the tree without changing its structure*.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/28/recover1.jpg)

<pre><code><strong>Input: root = [1,3,null,null,2]
</strong><strong>Output: [3,1,null,null,2]
</strong><strong>Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
</strong></code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/10/28/recover2.jpg)

<pre><code><strong>Input: root = [3,1,4,null,null,2]
</strong><strong>Output: [2,1,4,null,null,3]
</strong><strong>Explanation: 2 cannot be in the right subtree of 3 because 2 &#x3C; 3. Swapping 2 and 3 makes the BST valid.
</strong></code></pre>

&#x20;

**Constraints:**

* The number of nodes in the tree is in the range `[2, 1000]`.
* `-231 <= Node.val <= 231 - 1`

## Intuition

```
Approach 1: 
Brute 

Sorting and comparing with actual inorder traversal

Approach 2:
3 1 2
Two cases,
Swapping are adjacent, not adjacent

Swapping are not afjacent,
Maintain the pointers 
3 1 maintain 3->first, 1->middle 
2 2->last

Voilation of a < b BST condition

Else if adjacent
Hence maintaing two pointers first and middle,
To swap them if at end we find last as null
```

### Links

<https://leetcode.com/problems/recover-binary-search-tree/description/>

### Video Links

<https://www.youtube.com/watch?v=ZWGW7FminDM&ab_channel=takeUforward>

### Approach 1:

```
Brute
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<pair<TreeNode*, int>> inorder, temp;

    static bool comp(pair<TreeNode*, int> &a, pair<TreeNode*, int>&b){
        return a.second<b.second;
    }

    void traversal(TreeNode* root){
        if(root == nullptr)
            return ;

        traversal(root->left);
        inorder.push_back({root, root->val});
        temp.push_back({root, root->val});
        traversal(root->right);
    }
    
    void recoverTree(TreeNode* root) {
        traversal(root);

        sort(temp.begin(), temp.end(), comp);
        vector<TreeNode*> ans;

        for(int i=0; i<inorder.size(); i++){
            if(inorder[i].second != temp[i].second){
                inorder[i].first->val = temp[i].second;
                temp[i].first->val = inorder[i].second;
                return ;
            }
        }
    }
};
```

{% endcode %}

### Approach 2:

```
Optimal
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
private:
    TreeNode *prev = nullptr, *first = nullptr, *last = nullptr, *middle = nullptr;
    void inorder(TreeNode* root) {
        if (!root) 
            return;

        inorder(root->left);
        if (prev and root->val < prev->val) {
            if (first == nullptr) {
                first = prev;
                middle = root;
            }
            else    
                last = root;
        }
        
        prev = root;
        inorder(root->right);
    }
    
    
public:
    void recoverTree(TreeNode* root) {
        inorder(root);
        if(first and last)  swap(first->val, last->val);
        else    swap(first->val, middle->val);
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###