recover binary search tree
void correctBST( Node root )
{
// Initialize pointers needed
// for correctBSTUtil()
first = middle = last = prev = null;
// Set the pointers to find out
// two nodes
correctBSTUtil( root );
// Fix (or correct) the tree
if( first != null && last != null )
{
int temp = first.data;
first.data = last.data;
last.data = temp;
}
// Adjacent nodes swapped
else if( first != null && middle !=
null )
{
int temp = first.data;
first.data = middle.data;
middle.data = temp;
}
// else nodes have not been swapped,
// passed tree is really BST.
}