Recover Binary Search Tree Algorithm
The Recover Binary Search Tree Algorithm is a specialized algorithm designed to identify and correct a pair of misplaced nodes in a binary search tree (BST) that violates the BST property, which states that for every node, all the nodes in its left subtree should have smaller values, and all the nodes in its right subtree should have larger values. This corruption of the BST property could be a result of a previous insertion or deletion operation that failed to maintain the required ordering of nodes. The algorithm aims to restore the integrity of the binary search tree by finding the nodes that violate the BST property and swapping their values to correct the issue.
The Recover Binary Search Tree Algorithm typically involves the use of depth-first search (DFS) to traverse the tree in an in-order fashion, which visits the nodes in a sorted manner. During the traversal, the algorithm keeps track of the previous node visited and compares its value with the current node. If the previous node's value is greater than the current node's value, it means that the BST property is violated, and these nodes could be candidates for swapping. The algorithm continues the traversal and identifies the second misplaced node by finding another pair of nodes that violate the BST property. Once both misplaced nodes are identified, the algorithm swaps their values, thus restoring the binary search tree to its proper order. This approach has a time complexity of O(n) and can be further optimized using the Morris traversal technique, which eliminates the need for recursion or additional data structures.
// O(n) time, O(1) space
class Solution {
public:
void recoverTree(TreeNode *root) {
TreeNode* node = root;
TreeNode* prev = NULL;
TreeNode* prev1 = NULL;
TreeNode* curr1 = NULL;
TreeNode* prev2 = NULL;
TreeNode* curr2 = NULL;
while (node != NULL) {
if (node->left == NULL) {
prev = node;
node = node->right;
} else {
TreeNode* next = node->left;
while (next->right && next->right != node) {
next = next->right;
}
if (next->right == NULL) {
next->right = node;
node = node->left;
} else {
prev = node;
node = node->right;
next->right = NULL;
}
}
if (prev && node && prev->val > node->val) {
if (prev1 == NULL) {
prev1 = prev, curr1 = node;
} else {
prev2 = prev, curr2 = node;
}
}
}
if (prev1 && curr2) {
swap(prev1->val, curr2->val);
} else {
swap(prev1->val, curr1->val);
}
}
};
