99. Recover Binary Search Tree

Problem Statement

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.

Example 1:

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

Example 2:

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

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

C++

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 ;
            }
        }
    }
};

Approach 2:

Optimal

C++

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);
    }
};

Approach 3:

C++

Approach 4:

C++