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 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.