recover Binary Search Tree

XXX. Recover Binary Search Tree

Depth-First Search

Binary Search Tree

Problem Statement:

Two nodes of a Binary Search Tree (BST) are swapped by mistake. Write a function to recover the BST without changing its structure.

Algorithm:

The algorithm uses an in-order traversal to detect the two swapped nodes and swaps their values to restore the BST:

1. Perform an in-order traversal of the BST to visit nodes in ascending order.
2. Track the previous node (pred) during traversal. If a node is smaller than its predecessor, it violates the BST property.
3. Identify the first and second swapped nodes (x and y):
   • The first violation involves the first swapped node (x).
   • The second violation involves the second swapped node (y).
4. After traversal, swap the values of x and y to recover the BST.

Complexity:

Time Complexity: O(n), where n is the number of nodes in the BST.
Space Complexity: O(h), where h is the height of the BST (for the recursion stack).

Java Implementation:

class Solution {
    TreeNode x = null, y = null, pred = null; // Track swapped nodes and the predecessor

    public void swap(TreeNode a, TreeNode b) {
        int tmp = a.val; // Swap the values of two nodes
        a.val = b.val;
        b.val = tmp;
    }

    public void findTwoSwapped(TreeNode root) {
        if (root == null) return; // Base case for recursion

        // In-order traversal: process left subtree
        findTwoSwapped(root.left);

        // Detect swapped nodes
        if (pred != null && root.val < pred.val) {
            y = root; // Second node is the current node
            if (x == null) x = pred; // First node is the predecessor
            else return; // If both nodes are found, stop further traversal
        }

        pred = root; // Update the predecessor to the current node

        // In-order traversal: process right subtree
        findTwoSwapped(root.right);
    }

    public void recoverTree(TreeNode root) {
        findTwoSwapped(root); // Find the two swapped nodes
        swap(x, y); // Swap their values to recover the BST
    }
}

Explanation:

The algorithm uses an in-order traversal to identify the two nodes that violate the BST property. By swapping their values, the BST is restored without altering its structure.

• In-order Traversal: Ensures nodes are visited in ascending order for a valid BST.
• Swapped Nodes: Two nodes are identified based on violations of the in-order sequence.
• Recovery: Swapping the values of the identified nodes restores the BST.