Description:
You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Examples:
Example 1:
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
Example 2:
Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.Solution in Python:
To recover a binary search tree (BST) where exactly two nodes have been swapped by mistake, we need to identify these two nodes and swap their values back to correct the BST. We can achieve this using an in-order traversal of the tree, which should yield a sorted sequence if the tree is a valid BST.
For the problem constraints, we aim to solve it with O(1) space complexity (excluding the recursion stack). This can be done using Morris Traversal, which allows in-order traversal without extra space.
Python
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
# Initialize pointers needed for Morris Traversal
first_element = second_element = None
prev_element = TreeNode(float('-inf'))
# Helper function to swap values of two nodes
def swap(x, y):
x.val, y.val = y.val, x.val
# Morris Traversal to find the two nodes
current = root
while current is not None:
if current.left is None:
# Visit the node
if prev_element.val > current.val:
if first_element is None:
first_element = prev_element
second_element = current
prev_element = current
current = current.right
else:
# Find the rightmost node in the left subtree or the predecessor
predecessor = current.left
while predecessor.right is not None and predecessor.right is not current:
predecessor = predecessor.right
# Make current as the right child of its predecessor
if predecessor.right is None:
predecessor.right = current
current = current.left
else:
# Revert the changes made
predecessor.right = None
if prev_element.val > current.val:
if first_element is None:
first_element = prev_element
second_element = current
prev_element = current
current = current.right
# Swap the values of the two nodes to correct the tree
swap(first_element, second_element)Explanation of the Code
- Initialization:
first_elementandsecond_elementare pointers to the two nodes that need to be swapped.prev_elementis initialized to a very small value to keep track of the previous node during the in-order traversal.
- Morris Traversal:
currentstarts at the root of the tree.- If
currenthas no left child, it is visited directly. - If
currenthas a left child, find its predecessor (the rightmost node in the left subtree). - If the predecessor’s right child is
None, makecurrentthe right child of the predecessor and movecurrentto its left child. - If the predecessor’s right child is
current, revert the changes (i.e., remove the temporary link) and visitcurrent.
- Finding the Two Nodes:
- During the in-order traversal, if
prev_element.val > current.val, it means there is a violation of the BST property. - The first such violation identifies the
first_elementand possibly thesecond_element. - Any subsequent violation will identify the
second_element.
- During the in-order traversal, if
- Swapping the Nodes:
- After identifying the two misplaced nodes, swap their values to correct the BST.
This approach ensures that we achieve the desired O(1) space complexity by using Morris Traversal, and it correctly recovers the tree structure by identifying and swapping the two misplaced nodes.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var recoverTree = function(root) {
// Initialize pointers needed for Morris Traversal
let firstElement = null;
let secondElement = null;
let prevElement = new TreeNode(Number.NEGATIVE_INFINITY);
// Helper function to swap values of two nodes
const swap = (x, y) => {
let temp = x.val;
x.val = y.val;
y.val = temp;
};
// Morris Traversal to find the two nodes
let current = root;
while (current !== null) {
if (current.left === null) {
// Visit the node
if (prevElement.val > current.val) {
if (firstElement === null) {
firstElement = prevElement;
}
secondElement = current;
}
prevElement = current;
current = current.right;
} else {
// Find the rightmost node in the left subtree or the predecessor
let predecessor = current.left;
while (predecessor.right !== null && predecessor.right !== current) {
predecessor = predecessor.right;
}
// Make current as the right child of its predecessor
if (predecessor.right === null) {
predecessor.right = current;
current = current.left;
} else {
// Revert the changes made
predecessor.right = null;
if (prevElement.val > current.val) {
if (firstElement === null) {
firstElement = prevElement;
}
secondElement = current;
}
prevElement = current;
current = current.right;
}
}
}
// Swap the values of the two nodes to correct the tree
swap(firstElement, secondElement);
};Solution in Java:
Java
class Solution {
private TreeNode firstElement = null;
private TreeNode secondElement = null;
private TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
// Morris Traversal to find the two nodes
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// Visit the node
if (prevElement.val > current.val) {
if (firstElement == null) {
firstElement = prevElement;
}
secondElement = current;
}
prevElement = current;
current = current.right;
} else {
// Find the rightmost node in the left subtree or the predecessor
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
// Make current as the right child of its predecessor
if (predecessor.right == null) {
predecessor.right = current;
current = current.left;
} else {
// Revert the changes made
predecessor.right = null;
if (prevElement.val > current.val) {
if (firstElement == null) {
firstElement = prevElement;
}
secondElement = current;
}
prevElement = current;
current = current.right;
}
}
}
// Swap the values of the two nodes to correct the tree
swap(firstElement, secondElement);
}
private void swap(TreeNode x, TreeNode y) {
int temp = x.val;
x.val = y.val;
y.val = temp;
}
}Solution in C#:
C#
public class Solution {
private TreeNode firstElement = null;
private TreeNode secondElement = null;
private TreeNode prevElement = new TreeNode(int.MinValue);
public void RecoverTree(TreeNode root) {
// Morris Traversal to find the two nodes
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// Visit the node
if (prevElement.val > current.val) {
if (firstElement == null) {
firstElement = prevElement;
}
secondElement = current;
}
prevElement = current;
current = current.right;
} else {
// Find the rightmost node in the left subtree or the predecessor
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
// Make current as the right child of its predecessor
if (predecessor.right == null) {
predecessor.right = current;
current = current.left;
} else {
// Revert the changes made
predecessor.right = null;
if (prevElement.val > current.val) {
if (firstElement == null) {
firstElement = prevElement;
}
secondElement = current;
}
prevElement = current;
current = current.right;
}
}
}
// Swap the values of the two nodes to correct the tree
Swap(firstElement, secondElement);
}
private void Swap(TreeNode x, TreeNode y) {
int temp = x.val;
x.val = y.val;
y.val = temp;
}
}