> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/99-recover-binary-search-tree.md).

# 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

```cpp
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]);
}
```