Binary Search Trees Using the ordering
394. Recover Binary Search Tree
You are given root, the root node of a binary search tree in which the values of exactly two nodes were
swapped by mistake. Put those two values back where they belong. Do not change the shape of the tree. Your
function returns nothing: it changes the tree in place.
In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. The values in the tree are distinct.
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out. The output shows the tree after your function returns,
written the same way.
Example 1
Input: root = [30, 10, 50, 5, 40, 20, 60]
[30,10,50,5,20,40,60]Explanation: 40 sits in the left subtree of 30 but is larger than 30, and 20 sits in the right subtree but is smaller. These two values swapped places, so we swap them back.
Example 2
Input: root = [0, 1000000000, -1000000000]
[0,-1000000000,1000000000]Explanation: The root's two children hold each other's values. After the swap, −109 is on the left and 109 on the right.
Example 3
Input: root = [25, 10, 30, null, 15, 20]
[20,10,30,null,15,25]Explanation: 20 is in the right subtree of the root but smaller than the root's 25. The root and that node swap their values back.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
2 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
- The values are distinct, and swapping the values of exactly two nodes makes the tree a binary search tree.
Clarifying questions
What you would ask an interviewer before writing any code.