Recover Binary Search Tree
Recover Binary Search Tree is a medium trees & bst problem solved with the bst basics pattern.
The best approach, optimal (morris in-order traversal), runs in O(n) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (collect, sort, write back) up.
Problem
You are given the root of a binary search tree in which the values of exactly two nodes were swapped by mistake. Every other node is where it should be.
Fix the tree in place by putting the two values back, without changing the tree’s shape. The function returns nothing; the tree itself is checked afterwards.
Examples
Example 1
- Input
root = [4, 2, 6, 1, 5, 3, 7]- Output
[4, 2, 6, 1, 3, 5, 7]- Why
- The in-order sequence is 1, 2, 5, 4, 3, 6, 7. Values 5 and 3 are in each other's places, so swapping them restores the order.
Example 2
- Input
root = [2, null, 1]- Output
[1, null, 2]- Why
- The root and its right child hold each other's values.
Example 3
- Input
root = [3, 1, 4, null, null, 2]- Output
[2, 1, 4, null, null, 3]- Why
- In-order gives 1, 3, 2, 4: the swapped values 3 and 2 sit next to each other in that sequence.
Constraints
- The tree has
2to1000nodes. -2^31 <= Node.val <= 2^31 - 1, all values distinct.- Exactly two nodes have had their values swapped; everything else is a valid BST.
- Change the values in place; the shape of the tree must not change.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (collect, sort, write back) | O(n log n) | O(n) |
| Better (in-order with a previous pointer) | O(n) | O(h) |
| Optimal (Morris in-order traversal) | O(n) | O(1) |
1Brute force (collect, sort, write back)
O(n log n)Sorting the n values dominates; the two walks are linear.O(n)The list of values plus the recursion stack.Read all values with an in-order walk, sort them, then do a second in-order walk that writes the sorted values back node by node. The result is the only BST with this shape and these values, so the two swapped nodes end up fixed.
- In-order walk: append every value to a list.
- Sort the list.
- In-order walk again, assigning list[i++] to each node.
class Solution {
private List<Integer> vals = new ArrayList<>();
private int idx = 0;
public void recoverTree(TreeNode root) {
collect(root);
Collections.sort(vals);
idx = 0;
write(root);
}
private void collect(TreeNode node) {
if (node == null) return;
collect(node.left);
vals.add(node.val);
collect(node.right);
}
private void write(TreeNode node) {
if (node == null) return;
write(node.left);
node.val = vals.get(idx++);
write(node.right);
}
}class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
vals: List[int] = []
def collect(node: Optional[TreeNode]) -> None:
if node is None:
return
collect(node.left)
vals.append(node.val)
collect(node.right)
collect(root)
vals.sort()
idx = 0
def write(node: Optional[TreeNode]) -> None:
nonlocal idx
if node is None:
return
write(node.left)
node.val = vals[idx]
idx += 1
write(node.right)
write(root)class Solution {
public:
void recoverTree(TreeNode* root) {
vals.clear();
collect(root);
sort(vals.begin(), vals.end());
idx = 0;
write(root);
}
private:
vector<int> vals;
int idx = 0;
void collect(TreeNode* node) {
if (node == nullptr) return;
collect(node->left);
vals.push_back(node->val);
collect(node->right);
}
void write(TreeNode* node) {
if (node == nullptr) return;
write(node->left);
node->val = vals[idx++];
write(node->right);
}
};function recoverTree(root) {
const vals = [];
const collect = (node) => {
if (node === null) return;
collect(node.left);
vals.push(node.val);
collect(node.right);
};
collect(root);
vals.sort((a, b) => a - b);
let idx = 0;
const write = (node) => {
if (node === null) return;
write(node.left);
node.val = vals[idx++];
write(node.right);
};
write(root);
}2Better (in-order with a previous pointer)
O(n)Every node is visited once.O(h)The recursion stack is as deep as the tree height h (n for a chain).Walk the tree in order, remembering the previously visited node. Whenever prev.val > cur.val there is a drop. At the first drop the misplaced larger value is prev; at every drop the smaller value is cur, so after the walk the second node is the cur of the last drop. Swap the two values.
- first = second = prev = null.
- Recursive in-order: at each node, if prev != null and prev.val > node.val: if first is null set first = prev; set second = node.
- Set prev = node and continue.
- Swap first.val and second.val.
class Solution {
private TreeNode first, second, prev;
public void recoverTree(TreeNode root) {
first = second = prev = null;
inorder(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
if (prev != null && prev.val > node.val) {
if (first == null) first = prev;
second = node;
}
prev = node;
inorder(node.right);
}
}class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
self.first = self.second = self.prev = None
def inorder(node: Optional[TreeNode]) -> None:
if node is None:
return
inorder(node.left)
if self.prev is not None and self.prev.val > node.val:
if self.first is None:
self.first = self.prev
self.second = node
self.prev = node
inorder(node.right)
inorder(root)
self.first.val, self.second.val = self.second.val, self.first.valclass Solution {
public:
void recoverTree(TreeNode* root) {
first = second = prev = nullptr;
inorder(root);
swap(first->val, second->val);
}
private:
TreeNode* first = nullptr;
TreeNode* second = nullptr;
TreeNode* prev = nullptr;
void inorder(TreeNode* node) {
if (node == nullptr) return;
inorder(node->left);
if (prev != nullptr && prev->val > node->val) {
if (first == nullptr) first = prev;
second = node;
}
prev = node;
inorder(node->right);
}
};function recoverTree(root) {
let first = null, second = null, prev = null;
const inorder = (node) => {
if (node === null) return;
inorder(node.left);
if (prev !== null && prev.val > node.val) {
if (first === null) first = prev;
second = node;
}
prev = node;
inorder(node.right);
};
inorder(root);
const tmp = first.val;
first.val = second.val;
second.val = tmp;
}3Optimal (Morris in-order traversal)
O(n)Each edge is walked at most a constant number of times while threads are created and removed.O(1)Only a few pointers; the temporary threads reuse existing null right pointers.Do the same drop detection, but walk in order with Morris threading instead of recursion. For a node with a left subtree, find its in-order predecessor (rightmost node of the left subtree). If the predecessor's right pointer is empty, point it back at the node and go left; if it already points at the node, remove the thread, visit the node and go right. Every node is visited in sorted position with O(1) extra memory, and the tree is restored to its original shape.
- cur = root. While cur != null:
- If cur.left is null: visit cur, cur = cur.right.
- Else find pred = rightmost of cur.left (stopping if pred.right == cur). If pred.right is null: set pred.right = cur, cur = cur.left. Otherwise set pred.right = null, visit cur, cur = cur.right.
- Visiting compares with prev exactly as in the previous approach. Finally swap first.val and second.val.
class Solution {
public void recoverTree(TreeNode root) {
TreeNode first = null, second = null, prev = null, cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode pred = cur.left;
while (pred.right != null && pred.right != cur) pred = pred.right;
if (pred.right == null) {
pred.right = cur;
cur = cur.left;
continue;
}
pred.right = null;
}
if (prev != null && prev.val > cur.val) {
if (first == null) first = prev;
second = cur;
}
prev = cur;
cur = cur.right;
}
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
}class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
first = second = prev = None
cur = root
while cur is not None:
if cur.left is not None:
pred = cur.left
while pred.right is not None and pred.right is not cur:
pred = pred.right
if pred.right is None:
pred.right = cur
cur = cur.left
continue
pred.right = None
if prev is not None and prev.val > cur.val:
if first is None:
first = prev
second = cur
prev = cur
cur = cur.right
first.val, second.val = second.val, first.valclass Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *first = nullptr, *second = nullptr, *prev = nullptr, *cur = root;
while (cur != nullptr) {
if (cur->left != nullptr) {
TreeNode* pred = cur->left;
while (pred->right != nullptr && pred->right != cur) pred = pred->right;
if (pred->right == nullptr) {
pred->right = cur;
cur = cur->left;
continue;
}
pred->right = nullptr;
}
if (prev != nullptr && prev->val > cur->val) {
if (first == nullptr) first = prev;
second = cur;
}
prev = cur;
cur = cur->right;
}
swap(first->val, second->val);
}
};function recoverTree(root) {
let first = null, second = null, prev = null, cur = root;
while (cur !== null) {
if (cur.left !== null) {
let pred = cur.left;
while (pred.right !== null && pred.right !== cur) pred = pred.right;
if (pred.right === null) {
pred.right = cur;
cur = cur.left;
continue;
}
pred.right = null;
}
if (prev !== null && prev.val > cur.val) {
if (first === null) first = prev;
second = cur;
}
prev = cur;
cur = cur.right;
}
const tmp = first.val;
first.val = second.val;
second.val = tmp;
}Edge cases to test
- The two swapped nodes are neighbours in in-order (only one descent in the sequence)
- The root is one of the swapped nodes
- A two-node tree
- A completely skewed tree (a chain)
- Values at the ends of the int range
Hints
Hint 1
An in-order walk of a valid BST lists the values in increasing order. What does swapping two values do to that sorted sequence?
Hint 2
Look for places where a value is larger than the one after it. There are either two such drops or just one (when the swapped nodes are adjacent in the sequence).
Hint 3
The first wrong node is the larger value at the first drop; the second is the smaller value at the last drop. Morris traversal lets you walk in order without a stack, for O(1) extra space.
FAQ
What is the best time complexity for Recover Binary Search Tree?
Optimal (Morris in-order traversal) runs in O(n) time and O(1) extra space. Each edge is walked at most a constant number of times while threads are created and removed.
Which pattern does Recover Binary Search Tree use?
It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.
Is there a brute force solution for Recover Binary Search Tree?
Yes. Brute force (collect, sort, write back) takes O(n log n) time and O(n) space. Read all values with an in-order walk, sort them, then do a second in-order walk that writes the sorted values back node by node.
Which edge cases should I test for Recover Binary Search Tree?
The two swapped nodes are neighbours in in-order (only one descent in the sequence); The root is one of the swapped nodes; A two-node tree; A completely skewed tree (a chain); Values at the ends of the int range.