Solution Explanation: Recovering a Binary Search Tree

This problem involves correcting a binary search tree (BST) where exactly two nodes have their values swapped. The goal is to recover the BST without altering its structure. The most efficient solution uses an in-order traversal and a constant amount of extra space.

Approach:

A crucial property of a BST is that an in-order traversal yields a sorted sequence. If two nodes are swapped, the in-order traversal will produce a sequence with two inversions (where an element is smaller than its predecessor). The algorithm identifies these inversions and swaps the values of the incorrect nodes.

1. In-order Traversal: Perform an in-order traversal of the BST. During traversal:

   • Maintain a prev node to track the previously visited node.
   • If the current node's value is less than prev's value (inversion), this indicates a swap.
   • We use two variables, first and second, to store the nodes involved in the swap. first stores the first node of the inversion, and second stores the second (larger) node of the inversion.

2. Swap the Values: After the traversal, we have identified first and second nodes. We swap their values to correct the BST.

Time Complexity: O(N), where N is the number of nodes in the BST. This is because we perform a single in-order traversal.

Space Complexity: O(H), where H is the height of the BST. In the worst case (a skewed tree), H can be N, resulting in O(N) space complexity due to the recursive call stack. However, in a balanced BST, H is log₂N, making the space complexity O(log N). Many solutions presented optimize to use only a few variables, reducing space complexity to O(1) in terms of extra space usage.

Code Explanation (Python):

# 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: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
 
        def dfs(root):
            if root is None:
                return
            nonlocal prev, first, second # these are modified within the dfs function
            dfs(root.left)
            if prev and prev.val > root.val:
                if first is None:
                    first = prev
                second = root
            prev = root
            dfs(root.right)
 
        prev = first = second = None #initialize these to None.
        dfs(root)
        first.val, second.val = second.val, first.val #Swap the values

The dfs function performs the in-order traversal recursively. The nonlocal keyword allows modification of variables defined outside the nested function's scope. The main function initializes prev, first, and second, then calls dfs to traverse and identify the nodes to swap. Finally, it swaps the values of first and second.

Other Languages:

The code in Java, C++, Go, JavaScript, and C# follows the same logic and uses similar data structures to achieve the same solution. The key differences lie in syntax and specific language features (e.g., nonlocal in Python vs. instance variables in Java). The core algorithm remains consistent across all implementations.