The key is to keey a previous TreeNode,

Since it's a BST, inorder traversal gives us a sorted order. Whenever we finish visiting a node, we update the prev TreeNode

goLeft

root, update(prev)

goRight

```
void recoverTree(TreeNode* root)
{
if(root == NULL)
return;
TreeNode* node1 = NULL, *node2 = NULL, *previous = NULL;
traverse(root, parent, node1, node2);
if(node1!=NULL && node2!=NULL)
{
int tmp = node1->val;
node1->val = node2->val;
node2->val = tmp;
}
}
void traverse(TreeNode* root, TreeNode* & previous, TreeNode* & node1, TreeNode* & node2)
{
if(root == NULL)
return;
traverse(root->left, previous, node1, node2);
int val = root->val;
if(previous != NULL)
{
if( previous->val > root->val )
{
if(node1 == NULL)
{
node1 = previous;
node2 = root;
}
else
node2 = root;
}
}
previous = root;
traverse(root->right, previous, node1, node2);
}
```