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.