Recovering a Swapped Binary Search Tree

A binary search tree (BST) has two of its nodes swapped by mistake. The task is to restore the tree to its correct BST form without altering its structure. The challenge is to achieve this with constant space complexity (O(1) space), avoiding the use of a full in-order traversal list.

Approach

The key observation is that an in-order traversal of a valid BST produces a strictly increasing sequence of values. When two nodes are swapped, this sequence will have two violations where a previous value is greater than the current value. The first such violation identifies the first incorrect node, and the second violation identifies the second incorrect node. By swapping the values of these two nodes, the tree is restored.

Algorithm

1. Perform an in-order traversal of the tree.
2. Track the previously visited node (previousNode).
3. During traversal, if previousNode->val is greater than the current node's value, it indicates a violation.
   • If this is the first violation, mark the previousNode as the first incorrect node (firstIncorrectNode).
   • For any subsequent violation, mark the current node as the second incorrect node (secondIncorrectNode).
4. After the traversal, swap the values of firstIncorrectNode and secondIncorrectNode.

Code Example (C++)

#include <algorithm>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTRecoverer {
public:
    void fixSwappedNodes(TreeNode* root) {
        TreeNode* previousNode = nullptr;
        TreeNode* firstIncorrectNode = nullptr;
        TreeNode* secondIncorrectNode = nullptr;

        performInOrderTraversal(root, previousNode, firstIncorrectNode, secondIncorrectNode);

        if (firstIncorrectNode && secondIncorrectNode) {
            std::swap(firstIncorrectNode->val, secondIncorrectNode->val);
        }
    }

private:
    void performInOrderTraversal(TreeNode* currentNode, TreeNode*& previousNode, TreeNode*& firstIncorrectNode, TreeNode*& secondIncorrectNode) {
        if (!currentNode) {
            return;
        }

        // Traverse the left subtree
        performInOrderTraversal(currentNode->left, previousNode, firstIncorrectNode, secondIncorrectNode);

        // Process the current node
        if (previousNode) {
            if (previousNode->val > currentNode->val) {
                if (!firstIncorrectNode) {
                    firstIncorrectNode = previousNode;
                }
                secondIncorrectNode = currentNode;
            }
        }
        previousNode = currentNode;

        // Traverse the right subtree
        performInOrderTraversal(currentNode->right, previousNode, firstIncorrectNode, secondIncorrectNode);
    }
};

Validating a Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined by the following properties:

• The left subtree of a node contains only nodes with values less than the node's value.
• The right subtree of a node contains only nodes with values greater than the node's value.
• Both the left and right subtrees must also be binary search trees.

Approach

A simple and efficient way to validate a BST is to perform an in-order traversal. For a valid BST, the values obtained from the in-order traversal will be in a strictly increasing order. We can verify this property during the traversal.

Algorithm

1. Perform an in-order traversal of the tree.
2. Keep track of the previously visited node's value.
3. For each node visited, check if its value is greater than the previousNode's value.
   • If its not, the tree is not a valid BST. We can terminate early.
4. If the traversal completes without finding any violations, the tree is a valid BST.

Code Example (C++)

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTValidator {
public:
    bool isBinarySearchTree(TreeNode* root) {
        bool isValid = true;
        TreeNode* previousNode = nullptr;
        validateInOrder(root, previousNode, isValid);
        return isValid;
    }

private:
    void validateInOrder(TreeNode* currentNode, TreeNode*& previousNode, bool& isValid) {
        if (!currentNode || !isValid) {
            return;
        }

        // Traverse the left subtree
        validateInOrder(currentNode->left, previousNode, isValid);

        // Process the current node
        if (previousNode) {
            if (previousNode->val >= currentNode->val) {
                isValid = false;
                return; // Early termination
            }
        }
        previousNode = currentNode;

        // Traverse the right subtree
        validateInOrder(currentNode->right, previousNode, isValid);
    }
};