Recover Binary Search Tree — Solution in Python, Java & C++
Recover Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Recover Binary Search Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Microsoft and Bloomberg interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Microsoft, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree with distinct values in which exactly two nodes had their values swapped by mistake.
Repair the tree in place by swapping those two values back, without changing its shape, and return its root.
Example 1
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be the left child of 1. Swapping 1 and 3 makes the tree 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. Swapping 2 and 3 makes the tree valid.
Example 3
Input: root = [2,3,1]
Output: [2,1,3]
Explanation: The two children were swapped with each other.
Constraints
2 <= number of nodes <= 1000-2^31 <= Node.val <= 2^31 - 1all node values are distinctthe tree is a binary search tree after swapping exactly two values back
Follow-up: The direct way stores the in-order sequence in O(n) space. Can you do it with O(h) — or even O(1) — extra space?
Hints for Recover Binary Search Tree
Hint 1
The in-order sequence of a binary search tree is sorted; here it is sorted except that two values traded places.
Hint 2
Walk in order and look for positions where a value is smaller than the one just before it. There are one or two such drops.
Hint 3
The first misplaced node is the larger value at the first drop; the second is the smaller value at the last drop. Swap their values.
How to solve Recover Binary Search Tree
Swapping two entries of a sorted sequence creates one drop (if they were neighbours) or two; the misplaced values are the left side of the first drop and the right side of the last one.
Approach
- Walk the tree in order with an explicit stack, remembering the previously visited node.
- Whenever
prev.val > node.val: if no first node is recorded, recordprevas the first; in every case recordnodeas the second. - After the walk, swap the values of the first and second nodes.
- Return the root.
Why it works
Let the sorted in-order sequence have entries at positions i < j exchanged. The larger value now sits at i, so position i is followed by a smaller value — the first drop's left side is position i. The smaller value sits at j, preceded by something larger — the last drop's right side is position j. When j = i + 1 these are the same single drop, which is why second is overwritten at every drop while first is set only once.
Complexity
- Time —
O(n) - Space —
O(h) for the stack (Morris traversal brings it to O(1))
Pitfalls
- Adjacent swapped values produce only one drop; record both nodes from it.
- Swap the values, not the nodes — the shape must not change.
Reference solution
Python
from typing import Optional
def recoverTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
stack = []
node = root
prev = first = second = None
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
if prev is not None and prev.val > node.val:
if first is None:
first = prev
second = node
prev = node
node = node.right
first.val, second.val = second.val, first.val
return rootJava
public static TreeNode recoverTree(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root, prev = null, first = null, second = null;
while (!stack.isEmpty() || node != null) {
while (node != null) { stack.push(node); node = node.left; }
node = stack.pop();
if (prev != null && prev.val > node.val) {
if (first == null) first = prev;
second = node;
}
prev = node;
node = node.right;
}
int t = first.val;
first.val = second.val;
second.val = t;
return root;
}C++
TreeNode* recoverTree(TreeNode* root) {
vector<TreeNode*> stack;
TreeNode *node = root, *prev = nullptr, *first = nullptr, *second = nullptr;
while (!stack.empty() || node) {
while (node) { stack.push_back(node); node = node->left; }
node = stack.back();
stack.pop_back();
if (prev && prev->val > node->val) {
if (!first) first = prev;
second = node;
}
prev = node;
node = node->right;
}
swap(first->val, second->val);
return root;
}JavaScript
var recoverTree = function(root) {
var stack = [], node = root, prev = null, first = null, second = null;
while (stack.length > 0 || node !== null) {
while (node !== null) { stack.push(node); node = node.left; }
node = stack.pop();
if (prev !== null && prev.val > node.val) {
if (first === null) first = prev;
second = node;
}
prev = node;
node = node.right;
}
var t = first.val;
first.val = second.val;
second.val = t;
return root;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals