Given a binary search tree with 2 nodes swapped find number of pairs not following BST properties

Problem

Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property. Follow up - Fix the BST, in the next post.

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.    
  

```Now number of pairs not following BST property are 3. The reason is :  

*   10-20
*   10-8
*   20-8

###  Solution

**Method 1 - Using in-order traversal**  
We can have following solution:  

1.  Find the inorder traversal of the input tree. Example - 2, 5, 20, 10, 8
2.  Find the number of [inversions](http://k2code.blogspot.in/2013/08/inversions.html) in the inorder traversal. That is the answer. Here the inversions are 20-10, 20-8, and 10-8. 

Time complexity - O(n logn) as O(n) time for inorder traversal and O(nlogn) for number of inversions in the sorted array.

Problem

See also