Recover Binary Search Tree
Medium · Binary Search Trees · about 25 minutes
Asked at Microsoft, Amazon, Google, ByteDance.
Somebody exchanged the values of two nodes in a binary search tree, so it no longer satisfies the BST rule. Put the two values back where they belong, leaving the tree's shape as it is, and return the root.