Two elements of a binary search tree (BST) are swapped by mistake. Write a program to recover the tree without changing its structure.

Problem Note

  • A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Example 1

Input: Given BST where two elements are swapped by mistake
         10
        /  \
       5    8
      / \
     2   20
Output: Following is the output tree
         10
        /  \
       5    20
      / \
     2   8
Explanation: In the above input tree, nodes 20 and 8 must be swapped to fix the tree.

Example 2

Input: Given BST where two elements are swapped by mistake
  3
 / \
1   4
   /
  2
Output: Following is the output tree
  2
 / \
1   4
   /
  3