Recover BST: Finding Violations

In correct BST, inorder traversal is strictly increasing. After swap, there are violations.

Case 1: Adjacent swap (e.g., swap positions 3 and 4 in sorted order)

• One violation: prev > current at one point
• Swap prev and current

Case 2: Non-adjacent swap (e.g., swap positions 1 and 5)

• Two violations
• First violation: first = prev
• Second violation: second = current
• Swap first and second

def recoverTree(root):
    first = second = prev = null
    def inorder(node):
        nonlocal first, second, prev
        if not node: return
        inorder(node.left)
        if prev and prev.val > node.val:
            if not first:
                first = prev
            second = node
        prev = node
        inorder(node.right)
    inorder(root)
    first.val, second.val = second.val, first.val