Minimum Swaps to Convert a Binary Tree into a BST - Visualization
Problem Statement
Examples
Solution
Algorithm Steps
Code
C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left, *right;
};
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = node->right = NULL;
return node;
}
void inorder(struct TreeNode* root, int* arr, int* index) {
if (root == NULL) return;
inorder(root->left, arr, index);
arr[(*index)++] = root->val;
inorder(root->right, arr, index);
}
typedef struct {
int index;
int val;
} Pair;
int comparePairs(const void* a, const void* b) {
return ((Pair*)a)->val - ((Pair*)b)->val;
}
int minSwaps(int* arr, int n) {
Pair* arrPos = malloc(n * sizeof(Pair));
for (int i = 0; i < n; i++) {
arrPos[i].index = i;
arrPos[i].val = arr[i];
}
qsort(arrPos, n, sizeof(Pair), comparePairs);
int* visited = calloc(n, sizeof(int));
int swaps = 0;
for (int i = 0; i < n; i++) {
if (visited[i] || arrPos[i].index == i) continue;
int cycle_size = 0, j = i;
while (!visited[j]) {
visited[j] = 1;
j = arrPos[j].index;
cycle_size++;
}
if (cycle_size > 0) swaps += (cycle_size - 1);
}
free(arrPos);
free(visited);
return swaps;
}
int minSwapsToBST(struct TreeNode* root) {
int arr[100];
int index = 0;
inorder(root, arr, &index);
return minSwaps(arr, index);
}
int main() {
struct TreeNode* root = createNode(5);
root->left = createNode(6);
root->right = createNode(7);
root->left->left = createNode(8);
root->left->right = createNode(9);
printf("Minimum swaps required: %d\n", minSwapsToBST(root));
return 0;
}
Comments
Loading comments...