Recover Binary Search Tree

Problem: Recover Binary Search Tree

This problem requires a flexible usage of in-order traversal. In-order traversal actually arranges all the numbers in order so that we can see which 2 elements misunderstand their own orders. The first one should be bigger than its successor and the second one should be smaller than its predecessor. We can store the first one once we find it and keep searching until we met the second one.

Code in Python:

class Solution(object):
    def __init__(self):
        self.n1 = None
    self.n2 = None
    self.prev = None

    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        self.findBadNode(root)
        if self.n1 and self.n2:
            self.n1.val, self.n2.val = self.n2.val, self.n1.val

    def findBadNode(self, root):
        if not root:
            return
        self.findBadNode(root.left)
        if self.prev:
            if root.val < self.prev.val:
                if self.n1:
                    self.n2 = root
                else:
                    self.n1 = self.prev
                    self.n2 = root
        self.prev = root
        self.findBadNode(root.right)