Last Updated: 7 Feb, 2021
Minimum Swaps To Convert Binary Tree Into BST
Moderate
Asked in companies
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.
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.
Approaches
- 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.
- 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.