Recover Binary Search Tree

Problem Id: 99 Difficulty: Hard Tag: Tree Tag: Depth-first Search


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[1] = 5 is swapped because a[2] < a[1].

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)