Correct BST with two nodes swapped
Binary Search Trees
FAQs
Hard
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:
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.
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.
Input : root = [2, 1, 3, null, null, 4]
Constraints
- 1 <= Number of Nodes <= 104
- -231 <= Node.val <= 231 - 1
Hints
- "As we traverse in inorder (Left → Root → Right), the correct sequence should be in ascending order. If prev.val > curr.val, we found an out-of-order pair."
- "Perform Morris Traversal to detect swapped nodes in O(1) space. Identify two misplaced nodes during traversal. Swap their values to restore BST properties."
Company Tags
Snowflake
Epic Systems
Teladoc Health
Flipkart
Riot Games
Optum
Alibaba
Visa
ARM
KPMG
JPMorgan Chase
Rockstar Games
OYO Rooms
Shopify
Western Digital
Goldman Sachs
Splunk
Robinhood
AMD
IBM
Instacart
GE Healthcare
McKinsey & Company
HashiCorp
HCL Technologies
Google
Microsoft
Amazon
Meta
Apple
Netflix
Adobe
Editorial
Intuition
To fix a BST with two swapped nodes, the key is to recognize that an inorder traversal of a BST yields a sorted sequence. First, collect the node values using an inorder traversal, which will provide an array of values. Sorting this array reveals what the inorder sequence should be if the BST were correct. By comparing the BST's actual inorder traversal with this sorted array, it's possible to identify where the nodes are out of order. The task then is to correct these discrepancies by updating the BST nodes with the appropriate values from the sorted array, thereby restoring the BST's correct structure without altering its overall form.
Approach
- Perform an inorder traversal of the BST to gather the node values into an array. Sort this array to get the correct inorder sequence of the BST.
- Traverse the BST again using inorder traversal, comparing each node's value with the corresponding value in the sorted array.
- When a mismatch is found between a node's value and the value from the sorted array, update the BST node with the correct value from the sorted array.
- Return the modified BST.
Dry Run
Solution
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
#include <bits/stdc++.h>
using namespace std;
/**
* Definition for a binary tree node.
*/
struct TreeNode {
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
void recoverTree(TreeNode* root) {
// Initialize variables to keep track of the nodes to be swapped
TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;
// Helper function for inorder traversal
function<void(TreeNode*)> inorder = [&](TreeNode* node) {
if (!node) return;
// Traverse the left subtree
inorder(node->left);
// Identify the nodes that are out of order
if (prev && prev->data > node->data) {
if (!first) first = prev;
second = node;
}
// Update prev node to the current node
prev = node;
// Traverse the right subtree
inorder(node->right);
};
// Perform the inorder traversal to find the two nodes
inorder(root);
// Swap the values of the two nodes to correct the BST
if (first && second) {
swap(first->data, second->data);
}
}
};
// Helper function to insert nodes in the tree for testing purposes
TreeNode* insertLevelOrder(vector<int>& arr, int i) {
if (i >= arr.size() || arr[i] == -1) return nullptr;
TreeNode* root = new TreeNode(arr[i]);
root->left = insertLevelOrder(arr, 2 * i + 1);
root->right = insertLevelOrder(arr, 2 * i + 2);
return root;
}
// Helper function to print inorder traversal of the tree
void inorderPrint(TreeNode* root) {
if (root) {
inorderPrint(root->left);
cout << root->data << " ";
inorderPrint(root->right);
}
}
int main() {
// Example input tree: [1, 3, -1, -1, 2]
vector<int> nodes = {1, 3, -1, -1, 2};
TreeNode* root = insertLevelOrder(nodes, 0);
// Solution instance
Solution sol;
sol.recoverTree(root);
// Print corrected tree
inorderPrint(root);
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
/**
* Definition for a binary tree node.
*/
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int val) { data = val; left = null; right = null; }
}
class Solution {
// Initialize variables to keep track of the nodes to be swapped
private TreeNode first = null, second = null, prev = null;
public void recoverTree(TreeNode root) {
// Perform the inorder traversal to find the two nodes
inorder(root);
// Swap the values of the two nodes to correct the BST
if (first != null && second != null) {
int temp = first.data;
first.data = second.data;
second.data = temp;
}
}
private void inorder(TreeNode node) {
if (node == null) return;
// Traverse the left subtree
inorder(node.left);
// Identify the nodes that are out of order
if (prev != null && prev.data > node.data) {
if (first == null) first = prev;
second = node;
}
// Update prev node to the current node
prev = node;
// Traverse the right subtree
inorder(node.right);
}
// Main method to demonstrate the solution
public static void main(String[] args) {
// Example input tree: [1, 3, null, null, 2]
TreeNode root = new TreeNode(1);
root.left = new TreeNode(3);
root.left.right = new TreeNode(2);
// Solution instance
Solution sol = new Solution();
sol.recoverTree(root);
// Helper function to print inorder traversal of the tree
inorderPrint(root);
}
private static void inorderPrint(TreeNode root) {
if (root != null) {
inorderPrint(root.left);
System.out.print(root.data + " ");
inorderPrint(root.right);
}
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.data = val
self.left = left
self.right = right
class Solution:
def recoverTree(self, root):
"""
Recovers a binary search tree where two nodes have been swapped by mistake.
:param root: TreeNode, the root of the binary search tree
"""
# Initialize variables to keep track of the nodes to be swapped
self.first = self.second = self.prev = None
def inorder(node):
"""
Performs an inorder traversal to find the two swapped nodes.
:param node: TreeNode, the current node in the traversal
"""
if not node:
return
# Traverse the left subtree
inorder(node.left)
# Identify the nodes that are out of order
if self.prev and self.prev.data > node.data:
if not self.first:
self.first = self.prev
self.second = node
# Update prev node to the current node
self.prev = node
# Traverse the right subtree
inorder(node.right)
# Perform the inorder traversal to find the two nodes
inorder(root)
# Swap the values of the two nodes to correct the BST
if self.first and self.second:
self.first.data, self.second.data = self.second.data, self.first.data
# Main method to run the solution
if __name__ == "__main__":
# Helper function to insert nodes in the tree for testing purposes
def insertLevelOrder(arr, root, i, n):
if i < n:
temp = TreeNode(arr[i])
root = temp
root.left = insertLevelOrder(arr, root.left, 2 * i + 1, n)
root.right = insertLevelOrder(arr, root.right, 2 * i + 2, n)
return root
# Example input tree: [1, 3, null, null, 2]
nodes = [1, 3, None, None, 2]
root = None
root = insertLevelOrder(nodes, root, 0, len(nodes))
# Solution instance
sol = Solution()
sol.recoverTree(root)
# Helper function to print inorder traversal of the tree
def inorderPrint(root):
if root:
inorderPrint(root.left)
print(root.data, end=' ')
inorderPrint(root.right)
# Print corrected tree
inorderPrint(root)
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
/**
* Definition for a binary tree node.
*/
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.data = val;
this.left = left;
this.right = right;
}
}
class Solution {
recoverTree(root) {
// Initialize variables to keep track of the nodes to be swapped
this.first = null;
this.second = null;
this.prev = null;
// Helper function for inorder traversal
const inorder = (node) => {
if (!node) return;
// Traverse the left subtree
inorder(node.left);
// Identify the nodes that are out of order
if (this.prev && this.prev.data > node.data) {
if (!this.first) this.first = this.prev;
this.second = node;
}
// Update prev node to the current node
this.prev = node;
// Traverse the right subtree
inorder(node.right);
};
// Perform the inorder traversal to find the two nodes
inorder(root);
// Swap the values of the two nodes to correct the BST
if (this.first && this.second) {
let temp = this.first.data;
this.first.data = this.second.data;
this.second.data = temp;
}
}
}
// Helper function to insert nodes in the tree for testing purposes
function insertLevelOrder(arr, i) {
if (i >= arr.length || arr[i] === null) return null;
let root = new TreeNode(arr[i]);
root.left = insertLevelOrder(arr, 2 * i + 1);
root.right = insertLevelOrder(arr, 2 * i + 2);
return root;
}
// Helper function to print inorder traversal of the tree
function inorderPrint(root) {
if (root) {
inorderPrint(root.left);
process.stdout.write(root.data + ' ');
inorderPrint(root.right);
}
}
// Main method to demonstrate the solution
function main() {
// Example input tree: [1, 3, null, null, 2]
let nodes = [1, 3, null, null, 2];
let root = insertLevelOrder(nodes, 0);
// Solution instance
let sol = new Solution();
sol.recoverTree(root);
// Print corrected tree
inorderPrint(root);
console.log();
}
main();
Complexity Analysis
Time Complexity : O(N), where N is the number of nodes in the tree. The inorder traversal is performed once, visiting each node exactly once.
Space Complexity : O(H), where H is the height of the tree. The recursive call stack will have a maximum depth of H, which is the height of the tree.
Intuition
A Binary Search Tree (BST) has an inorder traversal that results in a sorted sequence. When two elements are swapped, this sorted order is disrupted. To identify these misplaced nodes, traverse the tree and keep track of the previous and next nodes for each visited node. By doing this, it's possible to detect where the order is violated. Once these violations are identified, the algorithm can pinpoint the two nodes that are out of place, whether they are adjacent or not. This allows for the correct nodes to be swapped, restoring the BST's proper structure.
Approach
- Use four pointers:
first,prev,middle, andlast.firstandmiddlehelp identify the misplaced nodes,prevtracks the previous node during the inorder traversal, andlastmarks the second node of the misplaced pair if the nodes are not adjacent. - Perform an inorder traversal of the BST, comparing each node's value with the previous node's value (
prev) to detect any violations where the current node's value is less than the previous node's value. When a violation is found:- The first violation identifies the
firstandmiddlenodes. Thefirstnode is the first element encountered that is not greater than its previous node, and themiddlenode is temporarily stored in case the swapped nodes are adjacent. - If a second violation occurs, it indicates that the swapped nodes are not adjacent, and the
lastnode is identified. - If no second violation is found, implying that the swapped nodes are adjacent, the
middlenode identified earlier is retained.
- The first violation identifies the
- Once the misplaced nodes are identified, perform the necessary swaps based on whether the nodes are adjacent or not:
- If both
firstandlastare identified, swap the values of thefirstandlastnodes. - If only
firstandmiddleare identified, swap their values.
- If both
Dry Run
Solution
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
#include <bits/stdc++.h>
using namespace std;
/**
* Definition for a binary tree node.
*/
struct TreeNode {
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *first = nullptr, *middle = nullptr, *last = nullptr, *prev = nullptr;
// Helper function for inorder traversal
function<void(TreeNode*)> inorder = [&](TreeNode* node) {
if (!node) return;
// Traverse the left subtree
inorder(node->left);
// Identify the nodes that are out of order
if (prev && prev->data > node->data) {
if (!first) {
first = prev; // First out-of-order node
middle = node; // Middle node in case nodes are adjacent
} else {
last = node; // Last out-of-order node
}
}
prev = node; // Update prev node to the current node
inorder(node->right); // Traverse the right subtree
};
inorder(root); // Perform the inorder traversal to find the two nodes
// Correct the BST by swapping the misplaced nodes
if (first && last) {
swap(first->data, last->data); // Non-adjacent nodes
} else if (first && middle) {
swap(first->data, middle->data); // Adjacent nodes
}
}
};
// Helper function to insert nodes in the tree for testing purposes
TreeNode* insertLevelOrder(vector<int>& arr, int i) {
if (i >= arr.size() || arr[i] == -1) return nullptr;
TreeNode* root = new TreeNode(arr[i]);
root->left = insertLevelOrder(arr, 2 * i + 1);
root->right = insertLevelOrder(arr, 2 * i + 2);
return root;
}
// Helper function to print inorder traversal of the tree
void inorderPrint(TreeNode* root) {
if (root) {
inorderPrint(root->left);
cout << root->data << " ";
inorderPrint(root->right);
}
}
int main() {
// Example input tree: [1, 3, -1, -1, 2]
vector<int> nodes = {1, 3, -1, -1, 2};
TreeNode* root = insertLevelOrder(nodes, 0);
// Solution instance
Solution sol;
sol.recoverTree(root);
// Print corrected tree
inorderPrint(root);
return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
/**
* Definition for a binary tree node.
*/
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int val) { data = val; left = null; right = null; }
}
class Solution {
private TreeNode first = null, middle = null, last = null, prev = null;
public void recoverTree(TreeNode root) {
inorder(root); // Perform inorder traversal to identify the misplaced nodes
// Correct the BST by swapping the misplaced nodes
if (first != null && last != null) {
int temp = first.data;
first.data = last.data;
last.data = temp;
} else if (first != null && middle != null) {
int temp = first.data;
first.data = middle.data;
middle.data = temp;
}
}
private void inorder(TreeNode node) {
if (node == null) return;
// Traverse the left subtree
inorder(node.left);
// Identify the nodes that are out of order
if (prev != null && prev.data > node.data) {
if (first == null) {
first = prev; // First out-of-order node
middle = node; // Middle node in case nodes are adjacent
} else {
last = node; // Last out-of-order node
}
}
prev = node; // Update prev node to the current node
// Traverse the right subtree
inorder(node.right);
}
// Main method to demonstrate the solution
public static void main(String[] args) {
// Example input tree: [1, 3, null, null, 2]
TreeNode root = new TreeNode(1);
root.left = new TreeNode(3);
root.left.right = new TreeNode(2);
// Solution instance
Solution sol = new Solution();
sol.recoverTree(root);
// Helper function to print inorder traversal of the tree
inorderPrint(root);
}
private static void inorderPrint(TreeNode root) {
if (root != null) {
inorderPrint(root.left);
System.out.print(root.data + " ");
inorderPrint(root.right);
}
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.data = val
self.left = left
self.right = right
class Solution:
def __init__(self):
# Initialize the pointers
self.first = None
self.first_next = None
self.last = None
self.previous_node = TreeNode(float('-inf')) # Previous node initialized to negative infinity
def inorderTraversal(self, root: TreeNode):
if not root:
return
# Traverse the left subtree
self.inorderTraversal(root.left)
# Identify misplaced nodes
if self.previous_node and root.data < self.previous_node.data:
if not self.first:
self.first = self.previous_node # First out-of-order node
self.first_next = root # Node next to the first out-of-order node
else:
self.last = root # Second out-of-order node
# Update previous node to current node
self.previous_node = root
# Traverse the right subtree
self.inorderTraversal(root.right)
def recoverTree(self, root: TreeNode):
# Reset the pointers
self.first = self.first_next = self.last = None
self.previous_node = TreeNode(float('-inf'))
# Perform the inorder traversal to find the two nodes
self.inorderTraversal(root)
# Correct the BST by swapping the misplaced nodes
if self.first and self.last:
self.first.data, self.last.data = self.last.data, self.first.data # Non-adjacent nodes
elif self.first and self.first_next:
self.first.data, self.first_next.data = self.first_next.data, self.first.data # Adjacent nodes
# Helper function to insert nodes in the tree for testing purposes
def insertLevelOrder(arr, i):
if i >= len(arr) or arr[i] is None:
return None
root = TreeNode(arr[i])
root.left = insertLevelOrder(arr, 2 * i + 1)
root.right = insertLevelOrder(arr, 2 * i + 2)
return root
# Helper function to print inorder traversal of the tree
def inorderPrint(root):
if root:
inorderPrint(root.left)
print(root.data, end=' ')
inorderPrint(root.right)
if __name__ == "__main__":
# Example input tree: [1, 3, None, None, 2]
nodes = [1, 3, None, None, 2]
root = insertLevelOrder(nodes, 0)
# Solution instance
sol = Solution()
sol.recoverTree(root)
# Print corrected tree
inorderPrint(root)
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394
/**
* Definition for a binary tree node.
*/
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.data = val;
this.left = left;
this.right = right;
}
}
class Solution {
constructor() {
// Initialize the pointers
this.first = null;
this.firstNext = null;
this.last = null;
this.previousNode = new TreeNode(Number.NEGATIVE_INFINITY); // Previous node initialized to negative infinity
}
inorderTraversal(node) {
if (!node) return;
// Traverse the left subtree
this.inorderTraversal(node.left);
// Identify misplaced nodes
if (this.previousNode && node.data < this.previousNode.data) {
if (!this.first) {
this.first = this.previousNode; // First out-of-order node
this.firstNext = node; // Node next to the first out-of-order node
} else {
this.last = node; // Second out-of-order node
}
}
// Update previous node to the current node
this.previousNode = node;
// Traverse the right subtree
this.inorderTraversal(node.right);
}
recoverTree(root) {
// Reset the pointers
this.first = this.firstNext = this.last = null;
this.previousNode = new TreeNode(Number.NEGATIVE_INFINITY);
// Perform the inorder traversal to find the two nodes
this.inorderTraversal(root);
// Correct the BST by swapping the misplaced nodes
if (this.first && this.last) {
[this.first.data, this.last.data] = [this.last.data, this.first.data]; // Non-adjacent nodes
} else if (this.first && this.firstNext) {
[this.first.data, this.firstNext.data] = [this.firstNext.data, this.first.data]; // Adjacent nodes
}
}
}
// Helper function to insert nodes in the tree for testing purposes
function insertLevelOrder(arr, i) {
if (i >= arr.length || arr[i] === null) return null;
const root = new TreeNode(arr[i]);
root.left = insertLevelOrder(arr, 2 * i + 1);
root.right = insertLevelOrder(arr, 2 * i + 2);
return root;
}
// Helper function to print inorder traversal of the tree
function inorderPrint(root) {
if (root) {
inorderPrint(root.left);
process.stdout.write(root.data + ' ');
inorderPrint(root.right);
}
}
// Main function to demonstrate the solution
const main = () => {
// Example input tree: [1, 3, null, null, 2]
const nodes = [1, 3, null, null, 2];
const root = insertLevelOrder(nodes, 0);
// Solution instance
const sol = new Solution();
sol.recoverTree(root);
// Print corrected tree
inorderPrint(root);
};
main();
Complexity Analysis
Time Complexity : O(N), traverses the binary tree once.
Space Complexity : O(N), in the worst case, the function call stack can go up to the depth of the tree, which is N nodes in an unbalanced tree.
Frequently Occurring Doubts
Q: Why are there exactly two misplaced nodes?
A: Because only two values were swapped, exactly two positions in inorder traversal will be incorrect.
Q: Why do we swap values instead of swapping nodes?
A: Swapping nodes changes tree structure, but swapping only values restores the BST without modifications.
Interview Followup Questions
Q: How would you modify the solution if nodes were swapped randomly, not just two?
A: Sort the inorder array and perform minimum swaps.
Q: Can this be solved iteratively using a stack?
A: Yes, using stack-based inorder traversal instead of recursion.
Notes
Code
✅ Testcase
Input: {'root': '1 3 null null 2'}
Expected:
3 1 null null 2 null null
3 1 null null 2 null null
Actual: -
Time: -
sec
Status: Waiting
Input: {'root': '3 1 4 null null 2'}
Expected:
2 1 4 null null 3 null null null
2 1 4 null null 3 null null null
Actual: -
Time: -
sec
Status: Waiting
Input: {'root': '5 6 7 2 null null 10'}
Expected:
6 5 7 2 null null 10 null null null null
6 5 7 2 null null 10 null null null null
Actual: -
Time: -
sec
Status: Waiting
Facts
- • Fun Fact: This problem mirrors a real-world issue that can occur in database recovery
- • Databases can sometimes experience inconsistencies due to errors, mistaken swaps, and so on
- • Programmers would need to rectify these inconsistencies without causing more errors by using algorithms similar to the solution of this problem
- • In fact, binary search trees, like the ones mentioned in the problem, are frequently used to store data in databases due to their efficient search, insert, and delete operations!