#include<bits/stdc++.h>
using namespace std;
// You are given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
class TreeNode {
    public:
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };


class Solution {
public:
    TreeNode* first = NULL;
    TreeNode*second = NULL;
    TreeNode*prev=NULL;
    void recover(TreeNode*root)
    {
        if(!root) return ;
        recover(root->left);

        if(prev!=NULL)
        {
            if(first==NULL and prev->val > root->val)
            {
                first = prev;
               
            }
            if(first !=NULL and prev->val > root->val)
            {
                second = root;
            }
            
        }
        prev = root;
        recover(root->right);

    }
    void recoverTree(TreeNode* root) {
        recover(root);
        swap(first->val, second->val);
        
    }
};