Given a binary search tree(BST) whose two elements 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 think of a better 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   5
   /
  2
Output: Following is the output tree
  2
 / \
1   5
   /
  3
Explanation: The recovered BST shows that the nodes with value 2 aand 3 were swapped in the given BST.