Two elements of a binary search tree (BST) are swapped by mistake. Write a program to recover the tree without changing its structure.
- A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
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.
Input: Given BST where two elements are swapped by mistake 3 / \ 1 4 / 2 Output: Following is the output tree 2 / \ 1 4 / 3