class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        # Variables to keep track of the two nodes to be swapped
        self.first = None
        self.second = None

        # Variable to keep track of the previous node in the In-Order traversal
        # We initialize it with a node having -infinity to handle the first comparison safely
        self.prev = TreeNode(float('-inf'))

        def inorder(node):
            if not node:
                return
            
            # 1. Visit left
            inorder(node.left)

            # 2. Visit Node (the check)
            # If the sorting is broken (prev is greater than current)
            if self.prev.val > node.val:
                # If it's the first time we've seen a violation:
                if not self.first:
                    self.first = self.prev # The larget value is the problem
                    self.second = node # The smaller value is the problem (tentatively)
                else:
                    # If this is the second time we've seen a violation:
                    self.second = node # The new smaller value is the actual second node
            # Update prev to current before moving on
            self.prev = node

            # 3. Visit Right
            inorder(node.right)
        
        # Run the traversal
        inorder(root)

        # Swap the values
        self.first.val, self.second.val = self.second.val, self.first.val

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        stack = []
        node = root
        
        prev = None # Tracks the previously visited node in-order
        first = None # The first node to be swapped
        second = None # The second node to be swapped
        
        while stack or node:
            # 1. Drill left (find the smallest remaining value)
            while node:
                stack.append(node)
                node = node.left
            
            # 2. Process the node (this is the "In-Order" part)
            node = stack.pop()
            
            # CHECK FOR VIOLATION
            if prev and prev.val > node.val:
                if not first:
                    first = prev
                    second = node # Tentative
                else:
                    second = node # Found the second drop
            
            # Update prev
            prev = node
            
            # 3. Go Right
            node = node.right
            
        # 4. Perform the single swap
        first.val, second.val = second.val, first.val