99 Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

The Idea: Run an in order traversal through the tree. Collect the nodes. It will always follow that there are two nodes within the container that need to be swapped. Find these nodes and swap their values.

Complexity: O(n) time and O(n) space

void inOrderTraverse(TreeNode *root, vector<TreeNode*> &nodes) {
    if (root) {
        inOrderTraverse(root->left, nodes);
        nodes.push_back(root);
        inOrderTraverse(root->right, nodes);
    }
}

void my_swap(TreeNode *r1, TreeNode *r2) {
    int temp = r1->val;
    r1->val = r2->val;
    r2->val = temp;
}

pair<int, int> findMisplacedElements(vector<TreeNode*> nodes) {
    assert(nodes.size() > 1);
    for (int i = nodes.size() - 1; i > 0; i--) {
        if (nodes[i]->val < nodes[i - 1]->val) {
            int j = i - 1;
            while (j >= 0 && nodes[i]->val < nodes[j]->val)
                j--;
            return { i, j + 1 };
        }
    }
}

void recoverTree(TreeNode* root) {
    static vector<TreeNode*> nodes;
    nodes.clear();
    inOrderTraverse(root, nodes);
    pair<int, int> misplaced = findMisplacedElements(nodes);
    my_swap(nodes[misplaced.first], nodes[misplaced.second]);
}