Microsoft Interview- Two elements of BST are swapped by mistake. You have to restore the tree without changing its structure.

Two elements of BST are swapped by mistake. You have to restore the tree without changing its structure.

Solution:

// incomplete solution

Node fixSwappedBST ( Node r, int min, int max, Node toFix){

// r - root node, r.val >= min && r.val <= max  and toFix is the node which needs to be fixed and was at a wrong   place in the left subtree of the common ancestor (of the swapped nodes)

 if(r==null) return null;
 if(r.val<min || r.val > max){ // wrong node, so fix it
   if(toFix != null) { // swap the nodes  
    int tmp = toFix.val; toFix.val=r.val; r.val=tmp;
   }
   else{ toFix = r; }
   fixSwappedBST(r.left, min..
 }
else{
  fixSwappedBST(r.left,  min, r.val,toFix);
  fixSwappedBST(r.right,r.val, max,toFix);
 }
}


Another approach:

Do a Pre-order traversal of the BST. It would be wrong at two places, identify those two positions in the Pre-order traversal. Identify the first element of the pair where it is out of order and the last element of the pair where it is again out of order.

In the next traversal, swap these two nodes. Would this work ??
Solution: http://www.geeksforgeeks.org/archives/23616
Reference: http://www.geeksforgeeks.org/archives/23088