# Recover Binary Search Tree

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.

### Solution

This is a **hard** problem to visualize and comeup with a solution if you look frm a graph standpoint. However, if you look at it from a list standpoint, it becomes much easier to visualize and come up with a solution.

Lets take this example list: `[1, 6, 3, 4, 5, 2, 7]`

. THe algorithm involves iterating each element in the list, making note of the first element that is out of place. In this case, it is `6`

. Then, we iterate the list again, making note of the last element that is out of place. In this case, it is `2`

. Finally, we swap the two elements.

Map this to a BST, and you will see that the algorithm works.

```
var recoverTree = function(root) {
var prev = null; // Previous node during inorder traversal
var first = null; // First misplaced node
var second = null; // Second misplaced node
var inorderTraversal = function(node) {
if (node === null) {
return;
}
// Traverse the left subtree
inorderTraversal(node.left);
// Visit the current node
if (prev !== null && prev.val > node.val) {
if (first === null) {
first = prev;
}
second = node;
}
prev = node;
// Traverse the right subtree
inorderTraversal(node.right);
};
// Perform the in-order traversal to identify the misplaced nodes
inorderTraversal(root);
// Swap the values of the misplaced nodes
var temp = first.val;
first.val = second.val;
second.val = temp;
};
```