### 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:

- Find the inorder traversal of the input tree. Example - 2, 5, 20, 10, 8
- Find the number of inversions in the inorder traversal. That is the answer. Here the inversions are 20-10, 20-8, and 10-8.

## 0 comments:

## Post a Comment