Recover Binary Search Tree
Medium · Trees · Tree · Depth-First Search · Binary Search Tree · Binary Tree
Problem
You are given the root of a binary search tree in which the values of exactly two nodes were swapped by mistake. All values are distinct.
Restore the tree in place, without changing its shape, so that it is a valid binary search tree again: every value in a node's left subtree smaller than the node's value, and every value in its right subtree larger. Return nothing; the tests read the tree back with to_level(root).
An O(n)-space solution is straightforward. Can you do it with O(1) extra space?
The tree is given in level order, with None for a missing child. from_level([5,8,9,2]) builds it and to_level(root) turns it back into a list.
Examples
Input: root = [5,8,9,2] Output: [8,5,9,2]
In order the values read 2, 8, 5, 9: one drop, 8 > 5. Swapping 8 and 5 gives 2, 5, 8, 9.
Input: root = [10,5,15,None,None,20,12] Output: [10,5,15,None,None,12,20]
In order: 5, 10, 20, 15, 12. The drops are 20 > 15 and 15 > 12, so 20 and 12 are swapped back.
Input: root = [3,1,4,None,None,2] Output: [2,1,4,None,None,3]
In order: 1, 3, 2, 4. The root 3 and the node 2 below 4 are neighbours in that order, so there is a single drop, 3 > 2; swapping them gives 1, 2, 3, 4.
Constraints
- 2 <= number of nodes <= 1000
- -2^31 <= Node.val <= 2^31 - 1
- values are distinct
- exactly two values are swapped
Approaches
- Sort the in-order values and write them back — time O(n log n), space O(n)
Follow-up
Morris traversal changes right pointers while it walks and puts them back afterwards. Why must the walk finish (instead of stopping as soon as both nodes are found) before the tree is handed back?
Related problems
Start free on Cariara · Coding problems · System design studio
