Repair Two Swapped Keys
MediumTrees
Problem
A binary search tree of distinct values was damaged: the values of exactly two nodes were swapped by mistake. Everything else, including the shape, is intact.
Swap those two values back so the tree is a valid search tree again, and return the root. Do not change the shape.
Example 1
- Input:
- root = [1, 3, null, null, 2]
- Output:
- [3, 1, null, null, 2]
3 cannot sit in the left subtree of 1; swapping 1 and 3 fixes it.
Example 2
- Input:
- root = [3, 1, 4, null, null, 2]
- Output:
- [2, 1, 4, null, null, 3]
2 is in the right subtree of 3; swapping 2 and 3 fixes it.
Constraints
- 2 ≤ number of nodes ≤ 1000
- -2^31 ≤ node.val ≤ 2^31 - 1
- Exactly two values are out of place.
Hint
Show the first hint
What does an in-order traversal of a valid search tree look like, and how does swapping two values break it?
Walkthrough
How to approach it
01Clarify before coding
- Are exactly two values swapped? Yes, always exactly one pair.
- Can I change the structure? No, only the two values.
- Can the two nodes be adjacent in sorted order? Yes, then there is only one drop.
02Brute force
Collect all values, sort them and write them back in in-order order.
Cost: O(n log n) time and O(n) space; it also rewrites every node rather than the two broken ones.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.