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

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))