Given a BST with 2 nodes swapped, fix it

Problem

Given a BST with 2 nodes swapped fix it.

Example
Consider the BST:

Following is the correct BST 
         10
        /  \
       5    20
      / \
     2   8

Now we swap  8 and 20, and BST is changed.

Input Tree:
         10
        /  \
       5    8
      / \
     2   20

In the above tree, nodes 20 and 8 must be swapped to fix the tree.  

In the previous post, we saw how many pairs in the input tree violate the BST property. Here we will fix it.

1. The swapped nodes are not adjacent in the inorder traversal of the BST.

 For example, Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}. 
 The inorder traversal of the given tree is 3 25 7 8 10 15 20 5 

If we observe carefully, during inorder traversal, we find node 7 is smaller than the previous visited node 25. Here save the context of node 25 (previous node). Again, we find that node 5 is smaller than the previous node 20. This time, we save the context of node 5 ( current node ). Finally swap the two node’s values.
2. The swapped nodes are adjacent in the inorder traversal of BST.

  For example, Nodes 7 and 8 are swapped in {3 5 7 8 10 15 20 25}. 
  The inorder traversal of the given tree is 3 5 8 7 10 15 20 25 

Unlike case #1, here only one point exists where a node value is smaller than previous node value. e.g. node 7 is smaller than node 8.

How to Solve? We will maintain three pointers, first, middle and last. When we find the first point where current node value is smaller than previous node value, we update the first with the previous node & middle with the current node. When we find the second point where current node value is smaller than previous node value, we update the last with the current node. In case #2, we will never find the second point. So, last pointer will not be updated. After processing, if the last node value is null, then two swapped nodes of BST are adjacent.

code:

 private void swap(Node a, Node b) {  
   if (n1 == null || n2 == null)  return;
   int tmp = a.val;  
   a.val = b.val;  
   b.val = tmp;  
 }  
   
 public void recoverTree(Node root) {  
   Node cur = root, pre = null, first = null, second = null;  
   // in order travesal should return a sorted list  
   Stack stack = new Stack();  
   while (cur != null) { // find the left most child  
     stack.push(cur);  
     cur = cur.left;  
   }  
   while (!stack.isEmpty()) {  
     cur = stack.pop();  

     // is it wrong?  
     if (pre != null && cur.val < pre.val) {  
       if (first == null) {  
         // the first wrong item should be the bigger one  
         first = pre;  
         second = cur; // there is a chance that the two were swapped  
       } else {  
         // the second wrong item should be the smaller one  
         second = cur;  
         break;  
       }  
     }  

     // go to right child and repeat  
     pre = cur;  
     cur = cur.right;  
     while (cur != null) {  
       stack.push(cur);  
       cur = cur.left;  
     }  
   }  
   
   swap(first, second);  
 }  

References

• http://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/