Given the root of a Binary search tree(BST), where exactly two nodes were swapped by mistake. Your task is to fix (or correct) the BST by swapping them back. Do not change the structure of the tree.
Note: It is guaranteed that the given input will form BST, except for 2 nodes that will be wrong. All changes must be reflected in the original Binary search tree(BST).
Input: root = [10, 5, 8, 2, 20]
Output: 1
Explanation: The nodes 20 and 8 were swapped.
Input: root = [5, 10, 20, 2, 8]
Output: 1
Explanation: The nodes 10 and 5 were swapped.
Constraints:
1 ≤ Number of nodes ≤ 103
Approach 01:
-
C++
-
Python
#include <vector>
#include <algorithm>
class Solution {
public:
// Vector to store pairs of node values and corresponding node pointers
vector<pair<int, Node*>> inorderNodes;
// Helper function to perform inorder traversal and store nodes in 'inorderNodes'
void inorderTraversal(Node* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
inorderNodes.push_back({root->data, root});
inorderTraversal(root->right);
}
// Function to fix the BST by swapping the two misplaced nodes
void correctBST(Node* root) {
// Perform inorder traversal and store nodes
inorderTraversal(root);
// Create a sorted copy of 'inorderNodes'
vector<pair<int, Node*>> sortedNodes = inorderNodes;
sort(sortedNodes.begin(), sortedNodes.end());
// Pointer to store the first misplaced node
Node* firstMisplacedNode = nullptr;
// Identify and correct the misplaced nodes
for (int i = 0; i < inorderNodes.size(); i++) {
if (inorderNodes[i].first != sortedNodes[i].first) {
if (firstMisplacedNode == nullptr) {
firstMisplacedNode = inorderNodes[i].second;
} else {
swap(firstMisplacedNode->data, inorderNodes[i].second->data);
return;
}
}
}
}
};
class Solution:
def __init__(self):
self.inorderNodes = []
def inorderTraversal(self, root):
if root is None:
return
self.inorderTraversal(root.left)
self.inorderNodes.append((root.data, root))
self.inorderTraversal(root.right)
def correctBST(self, root):
self.inorderNodes = []
self.inorderTraversal(root)
sortedNodes = sorted(self.inorderNodes, key=lambda x: x[0])
firstMisplacedNode = None
for i in range(len(self.inorderNodes)):
if self.inorderNodes[i][0] != sortedNodes[i][0]:
if firstMisplacedNode is None:
firstMisplacedNode = self.inorderNodes[i][1]
else:
firstMisplacedNode.data, self.inorderNodes[i][1].data = (
self.inorderNodes[i][1].data,
firstMisplacedNode.data,
)
return
Time Complexity:
- Inorder Traversal:
Traversing the BST takes \( O(N) \).
- Sorting:
Sorting the collected nodes takes \( O(N \log N) \).
- Finding Misplaced Nodes:
Identifying and swapping misplaced nodes takes \( O(N) \).
- Overall Time Complexity:
\( O(N \log N) \) (due to sorting being the dominant operation).
Space Complexity:
- Storage for Nodes:
The vector
inorderNodesstores \( N \) elements, leading to \( O(N) \) space usage. - Sorted Copy:
An additional vector
sortedNodesalso requires \( O(N) \) space. - Auxiliary Variables:
A few pointers and integers are used, contributing \( O(1) \) extra space.
- Overall Space Complexity:
\( O(N) \).