Problem statement

https://binarysearch.com/problems/Binary-Search-Tree-Typo/

Solution

Equal to Leetcode Leetcode 0099. Recover Binary Search Tree.

Complexity

It is O(n) for time and O(1) for additional space. If we do not need O(1) space, just use inorder traversal.

Code

class Solution:
    def solve(self, root):
        cur, node, cands = root, Tree(-float("inf")), []
        while cur:
            if cur.left:
                pre = cur.left
                while pre.right and pre.right != cur:
                    pre = pre.right
                if not pre.right:
                    pre.right = cur
                    cur = cur.left
                else:
                    pre.right = None
                    if cur.val < node.val:
                        cands += [node, cur]
                    node = cur
                    cur = cur.right
            else:
                if cur.val < node.val:
                    cands += [node, cur]
                node = cur
                cur = cur.right
            
        cands[0].val, cands[-1].val = cands[-1].val, cands[0].val
        return root