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.
# 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)