Q99. Recover Binary Search Tree

You are given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

 

Example 1:


Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
Example 2:


Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
 

Constraints:

The number of nodes in the tree is in the range [2, 1000].
-231 <= Node.val <= 231 - 1

Here I focus on the solution with $O(N)$ space complexity, which definitely falls into the category of “need to know”.

The whole point is about performing the in-order traverse of the BST. If the BST is valid, the in-order traverse will result in an ascending order sequence. Whereas, if the BST is not valid, the resulting sequence won’t be ascending and as stated in the question, it should be fixed by a simple swap. For instance, if we have 0, 1, 4, 3, 2, 5, 6, we can easily see that 4 and 2 are swapped. This means that suppose we have the sequence, we could identify the pair to swap by extracting all the pairs with wrong order and extract the first and the last number of these pairs.

So, all the point of this question is to have in-order traverse in mind clearly. To have it briefly reviewed, the in-order traverse procedure is:

• Maintain a stack of node to visit.
• At a current node, push itself to the to-visit stack and go to its left child until there exists no more left child.
• Go to the top of the stack, visit that node and set its right child as current node.

The Python submission is.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # do in order traverse
        left_most = TreeNode(val=-float('inf'))
        to_visit = []
        prev = left_most
        mistake = []
        curr = root
        while curr is not None or len(to_visit) > 0:
            while curr is not None:
                to_visit.append(curr)
                curr = curr.left
            node = to_visit.pop()
            # print(node.val)
            if node.val < prev.val:
                mistake.append(prev)
                mistake.append(node)
            prev = node
            curr = node.right
        tmp = mistake[0].val
        mistake[0].val = mistake[-1].val
        mistake[-1].val = tmp
        return root

NOTE: the $O(1)$ space complexity solution is about improving the in-order traverse. This question is related to Q94. Binary Tree Inorder Traversal which is discussed in this post.