RecoverBST

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Idea:

This question is not hard to understand, but you must think about it carefully. How can you detect the two dis-ordered elements?

The most straightforward idea is to do an in-order traverse from the beginning to the end. When you detect that a node is larger then the next one, then that node is the first disordered element.

But, how can you detect the second disordered elements? Maybe you can do another in-order traverse from the back to the front, and detect the first one that is larger then its next one. This is not necessary.

When two nodes interchange in a BST, it must be that a larger one comes first, and the smaller one comes later, and that smaller one must be the minimum of the remaining nodes! Then you find it. In the end, you just modify the value of the two nodes.

Java: BinaryTree

public class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;
   TreeNode(int x) { val = x; }
}

Java: RecoverBST

01 public void recoverTree(TreeNode root) {
02      Stack<TreeNode>st=new Stack<TreeNode>();
03      TreeNode first=null;
04      TreeNode second=null;
05      int min=root.val;
06      if(root!=null)
07      {
08          st.push(root);
09          while(root.left!=null)
10          {
11              root=root.left;
12              st.push(root);
13          }          
14      }
15     
16      while(!st.empty())
17      {
18          TreeNode top=st.pop();          
19          TreeNode curr=top;
20          TreeNode next=curr;          
21          if(curr.right!=null)
22          {
23              st.push(curr.right);
24              curr=curr.right;
25              while(curr.left!=null)
26              {
27                  st.push(curr.left);
28                  curr=curr.left;                  
29              }
30          }
31         
32          if(!st.empty())
33          {
34              next=st.peek();
35          }
36         
37          if(top.val>next.val && first==null)
38          {
39              first=top;
40              second=next;
41              min=next.val;
42          }              
43         
44          if(first!=null && top.val<=min)
45          {
46              min=top.val;
47              second=top;
48          }
49      }
50     
51      int temp=first.val;
52      first.val=second.val;
53      second.val=temp;
54  }