Minimum Swaps To Convert Binary Tree Into BST

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
24 upvotes
Asked in companies
AmazonIntuit

Problem statement

You are given an arbitrary array of ‘N’ nodes which represents a complete binary tree, which means, for a node at index ‘i’, its left child will be at index (2 * i + 1) and right child will be at index (2 * i + 2).

You have to find the minimum number of swaps to convert this tree into a binary search tree.

Binary search tree is a binary tree where for any given root, all the values in the left subtree are smaller than the value of root and all the values in the right subtree are greater than or equal to the value of the root.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains a single integer T, representing the number of test cases.

The first line of each test case contains an integer N, which denotes the number of nodes in the tree.

The second line of each test case contains N space-separated integers denoting the node values.

Output Format :

For each test case, print a single integer which denotes the minimum number of swaps required to convert the given tree into a BST. The output of each test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 3000
1 <= arr[i] <= 10^5   

Where T are the number of test cases and N is the number of nodes in the tree.

Sample Input 1 :

2
7
1 2 3 4 5 6 7
3
1 2 3

Sample Output 1 :

3
1

Explanation for sample input 1 :

For the first test case, the given tree is :


Swap 1: Swap node 4 with 1.
Swap 2: Swap node 5 with 6.
Swap 3: Swap node 6 with 3.
After swapping, the tree will become


For the second test case, the given tree is


We can swap node 3 with 1 to get the BST, hence the number of swaps is 1.

Sample Input 2 :

1
4
4 3 2 1

Sample Output 2 :

2
Hint

Try to use inorder traversal to find the answer.

Approaches (1)
Inorder Traversal
  • Since we have to convert the binary tree to BST, we can use the fact that the in-order traversal of the BST is sorted in non-decreasing order.
  • Hence the problem reduces to find the minimum number of swaps to sort the inorder of the given binary tree.
  • Firstly, we can store the inorder traversal in the array ‘inorder’.
  • Create a vector of pairs ‘toSwap’, where the first value each index ‘i’ of toSwap will be inorder[i] and the second value will be ‘i’.
  • Now sort ‘toSwap’ according to the first value of each pair.
  • Let ‘ans’ = 0, denote the minimum number of swaps.
  • For i = 0 to i = n - 1, do the following:
    • For each value of the pair, if the second element is not equal to i, which means that the current element is not at its correct place,  so swap them, i.e.
      • swap(toSwap[i].first,toSwap[toSwap[i].second].first)
      • swap(toSwap[i].second,toSwap[toSwap[i].second].second)
    • If even after the swaps, the second element is not equal to i, then we decrement i, i.e. do i = i - 1.
    • Increment the ‘ans’ by 1.
Time Complexity

O(N * log N + N), where N is the number of nodes in the tree.

 

It will be O(N * log N + N) because we are sorting the array of size N. We will have extra O(N) because we are copying the elements from one vector to another.

Space Complexity

O(N), where N is the number of nodes in the tree.

 

We are creating an array to store the pair of values and their corresponding index. Thus, the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Swaps To Convert Binary Tree Into BST
Full screen
Console