Binary TreesProblem 21 of 35
Find minimum swaps required to convert a Binary tree into BST
Problem Statement
Given a binary tree, find the minimum number of swaps required to convert it into a Binary Search Tree (BST). A swap operation exchanges values of two nodes.
Example:
Input:
5
/ \
6 7
/ \
8 9
Inorder traversal: [8, 6, 9, 5, 7]
Sorted inorder: [5, 6, 7, 8, 9]
Output: 3
- Swap 8 and 5 → [5, 6, 9, 8, 7]
- Swap 9 and 7 → [5, 6, 7, 8, 9]
- Wait, that's 2 swaps... Let me recalculate with cycle detection
The problem reduces to finding minimum swaps to sort an array.
Approach 1: Brute Force (Selection Sort Style)
Intuition
First, get the inorder traversal of the tree. For a BST, inorder traversal should be sorted. The problem becomes finding minimum swaps to sort an array. Use selection sort style: for each position, find the minimum element and swap if needed.
Algorithm
- Perform inorder traversal to get array
- For each position i, find minimum in remaining array
- If minimum is not at position i, swap and increment count
- Return total swap count
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorder(TreeNode root, List<Integer> arr) {
if (root == null) return;
inorder(root.left, arr);
arr.add(root.val);
inorder(root.right, arr);
}
private int minSwapsBruteForce(int[] arr) {
int n = arr.length;
int swaps = 0;
for (int i = 0; i < n - 1; i++) {
// Find minimum element in remaining array
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Swap if needed
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
swaps++;
}
}
return swaps;
}
public int minSwaps(TreeNode root) {
List<Integer> list = new ArrayList<>();
inorder(root, list);
int[] arr = list.stream().mapToInt(i -> i).toArray();
return minSwapsBruteForce(arr);
}
}Complexity Analysis
- Time Complexity: O(n^2) - Selection sort takes O(n^2)
- Space Complexity: O(n) - For storing inorder traversal
Approach 2: Optimal (Cycle Detection)
Intuition
The minimum number of swaps to sort an array equals (total elements in all cycles) - (number of cycles). Create pairs of (value, target_index), sort them, and detect cycles. Each cycle of length k requires k-1 swaps.
Algorithm
- Perform inorder traversal to get array
- Create pairs of (value, original_index)
- Sort pairs by value to get target positions
- Detect cycles using visited array
- For each cycle of length k, add (k-1) to swap count
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorder(TreeNode root, List<Integer> arr) {
if (root == null) return;
inorder(root.left, arr);
arr.add(root.val);
inorder(root.right, arr);
}
private int minSwapsOptimal(int[] arr) {
int n = arr.length;
// Create pairs of (value, original index)
int[][] pairs = new int[n][2];
for (int i = 0; i < n; i++) {
pairs[i][0] = arr[i];
pairs[i][1] = i;
}
// Sort by value to get target positions
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
// Detect cycles
boolean[] visited = new boolean[n];
int swaps = 0;
for (int i = 0; i < n; i++) {
// Skip if already visited or already in correct position
if (visited[i] || pairs[i][1] == i) {
continue;
}
// Count cycle size
int cycleSize = 0;
int j = i;
while (!visited[j]) {
visited[j] = true;
j = pairs[j][1];
cycleSize++;
}
// Cycle of size k requires k-1 swaps
if (cycleSize > 1) {
swaps += (cycleSize - 1);
}
}
return swaps;
}
public int minSwaps(TreeNode root) {
List<Integer> list = new ArrayList<>();
inorder(root, list);
int[] arr = list.stream().mapToInt(i -> i).toArray();
return minSwapsOptimal(arr);
}
}Complexity Analysis
- Time Complexity: O(n log n) - Dominated by sorting
- Space Complexity: O(n) - For storing pairs and visited array
Key Takeaways
- BST property: Inorder traversal of BST is sorted
- Problem reduction: Convert tree to BST = Sort inorder array with minimum swaps
- Cycle detection: Minimum swaps = sum of (cycle_length - 1) for all cycles
- Why cycles work: In a cycle, each swap puts one element in correct position; k elements need k-1 swaps
- This pattern applies to: Any "minimum swaps to sort" problem