Find Minimum Swaps Required to Convert a Binary Tree into a BST

Algorithm Steps

Perform an inorder traversal of the binary tree to extract an array of node values. This array represents the tree's current order.
Create an array of pairs where each pair contains the node's value and its original index in the inorder array.
Sort this array of pairs based on the value to obtain the order that the BST would have.
Initialize a visited array (or equivalent) to keep track of processed indices.
Iterate through the sorted pairs and for each index not yet visited, count the size of the cycle formed by repeatedly mapping indices from the sorted order to the original order.
The number of swaps required for that cycle is (cycle size - 1). Sum up the swaps for all cycles to get the minimum number of swaps.

Minimum Swaps Required to Convert a Binary Tree into a BST - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root, arr):
    if root:
        inorder(root.left, arr)
        arr.append(root.val)
        inorder(root.right, arr)

def minSwaps(arr):
    n = len(arr)
    arrPos = list(enumerate(arr))
    arrPos.sort(key=lambda x: x[1])
    visited = [False] * n
    swaps = 0
    for i in range(n):
        if visited[i] or arrPos[i][0] == i:
            continue
        cycle_size = 0
        j = i
        while not visited[j]:
            visited[j] = True
            j = arrPos[j][0]
            cycle_size += 1
        if cycle_size > 0:
            swaps += (cycle_size - 1)
    return swaps

def minSwapsToBST(root):
    inorder_arr = []
    inorder(root, inorder_arr)
    return minSwaps(inorder_arr)

# Example usage:
if __name__ == '__main__':
    # Construct a binary tree:
    #         5
    #        / \
    #       6   7
    #      / \
    #     8   9
    root = TreeNode(5, TreeNode(6, TreeNode(8), TreeNode(9)), TreeNode(7))
    print('Minimum swaps required:', minSwapsToBST(root))