Problem

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

Follow up: Recover Binary Search Tree

Examples

Example 1

Consider the BST:

1
2
3
4
5

         10
        /  \
       5    (8)
      / \
     2   (20)

1
2
3

Input: root = [10,5,8,2,20]
Output:[[10, 20], [10, 8], [20, 8]]
Explanation: We swap  8 and 20, and BST is changed (marked in example above). Now,

Solution

Method 1 - Inorder 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. 

Complexity

  • Time: O(n log n) as O(n) time for inorder traversal and O(nlogn) for number of inversions in the sorted array.
  • Space: O(1)