# Recover Binary Search Tree    ## Intuition

By in-order traversal, we could traverse this Binary Search Tree just like an array. So this problem becomes like finding 2 elements which are swapped in a sorted array.

Let's see an example where 2 and 5 are swapped.:

```a = [1, 5, 3, 4, 2, 6, 7]
```

In this case, first, we could find the first element a = 5 is swapped because a < a.

Then, we need to find the second element. Since the first element is already here at 1, the second element must be in a[1:] and who is the smallest element.

## Solution

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def recoverTree(self, root: TreeNode) -> None:
self.first = None
self.second = None
self.tmp = TreeNode(float('-inf'))
self.inorder_traversal(root)
self.first.val, self.second.val = self.second.val, self.first.val

def inorder_traversal(self, node):
if node is None:
return
self.inorder_traversal(node.left)

if self.first is None:
if node.val < self.tmp.val:
self.first = self.tmp
self.second = node
else:
self.tmp = node
else:
if node.val < self.second.val:
self.second = node

self.inorder_traversal(node.right)

``````