Recover a Binary Search Tree

A Binary Search Tree (BST) is a tree data structure where the value of each node is greater than all values in its left subtree and less than all values in its right subtree. Sometimes, a BST can become corrupted, meaning two of its nodes have been swapped. Your task is to recover the original BST by swapping the values of these two nodes. This problem is useful for understanding tree traversal and manipulation, and for debugging scenarios where BST integrity is compromised.

Problem Description

You are given the root of a corrupted BST. Your goal is to correct the BST by swapping the values of exactly two nodes. You are not allowed to modify the structure of the tree (i.e., parent/child pointers). You must identify the two nodes whose values are swapped and swap their values to restore the BST property.

What needs to be achieved:

1. Identify the two nodes whose values are swapped.
2. Swap the values of these two nodes.
3. Return the root of the recovered BST.

Key Requirements:

• The input is a BST that has been corrupted by swapping exactly two nodes.
• The tree may contain duplicate values.
• You must restore the BST property without changing the tree structure.
• The solution should be efficient in terms of time and space complexity.

Expected Behavior:

The function should take the root of the corrupted BST as input and return the root of the recovered BST. The recovered tree should satisfy the BST property.

Edge Cases to Consider:

• Empty tree (root is null).
• Tree with only one node.
• Tree with duplicate values.
• The two swapped nodes might be close together or far apart in the tree.
• The two swapped nodes might be leaf nodes.

Examples

Example 1:

Input:
    3
   / \
  1   4
     / \
    2   5

(Corrupted BST where 1 and 3 are swapped)

Output:

    3
   / \
  2   4
     / \
    1   5

Explanation: Nodes with values 1 and 3 were swapped. Swapping their values restores the BST property.

Example 2:

Input:
    1
     \
      2
       \
        3

(Corrupted BST where 2 and 3 are swapped)

Output:

    1
     \
      3
       \
        2

Explanation: Nodes with values 2 and 3 were swapped. Swapping their values restores the BST property.

Example 3: (Edge Case - Duplicate Values)

Input:
    1
   / \
  1   3
     / \
    2   2

Output:

    1
   / \
  1   3
     / \
    2   2

Explanation: In this case, the tree is already a valid BST, even though it contains duplicate values. No swap is needed.

Constraints

• The number of nodes in the tree will be between 1 and 1000.
• The values of the nodes will be integers within the range of -1000 to 1000.
• The tree is guaranteed to be a corrupted BST, meaning exactly two nodes have been swapped.
• The time complexity should be O(N), where N is the number of nodes in the tree.
• The space complexity should be O(N) in the worst case (due to recursion stack).

Notes

• An in-order traversal of a BST yields a sorted list of values. You can use this property to identify the two swapped nodes.
• Keep track of the nodes encountered during the in-order traversal, along with their values.
• When you find a value that is out of order, you've found one of the swapped nodes.
• Continue the in-order traversal to find the second swapped node.
• After identifying the two swapped nodes, simply swap their values.
• Consider using a list to store the in-order traversal of the tree. This allows for easy identification of out-of-order elements.
• Be mindful of duplicate values when identifying the swapped nodes.