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

Problem Statement❯

Given a binary tree (not necessarily a binary search tree), find the minimum number of swaps required to convert it into a Binary Search Tree (BST). The conversion must preserve the original structure of the binary tree (i.e., only node values can be rearranged, not the structure).

Examples❯

Input Tree	Minimum Swaps	Description
[5, 6, 7, 8, 9, 10, 11]	3	Inorder of input is [8,6,9,5,10,7,11] → After sorting [5,6,7,8,9,10,11], minimum swaps = 3 (swap 8↔5, 9↔7, 10↔8)
[1, 2, 3]	0	Inorder is already sorted: [2,1,3] → Correct inorder should be [1,2,3]. Only 1 swap (2↔1), so answer = 1
[5, 3, 7, 1, 4, 6, 8]	0	This tree is already a BST. Inorder traversal is [1,3,4,5,6,7,8], so no swaps needed.
[1, 3, 2]	1	Inorder = [3,1,2] → Sorted = [1,2,3] → Swap 3↔1 gives correct order. Minimum swaps = 1
[10]	0	Single-node tree is trivially a BST. No swaps required.
[]	0	Empty tree has no elements. No swaps needed.

Solution❯

Case 1: Normal Binary Tree

When the binary tree is arbitrary and not sorted in any specific way, we first extract its inorder traversal, which reflects the order in which values would appear if the tree were a BST. However, this inorder array is often unsorted. To convert it into a BST, we calculate how many swaps are needed to sort this array.

We map each value with its original index, sort the array based on values, and find cycles in the index mappings. Each cycle of size k requires k - 1 swaps. Summing over all such cycles gives us the total minimum swaps required.

Case 2: Tree Already in BST Form

Even if a tree is a BST by structure, the problem only considers the values in the inorder array, so it may still require swaps if the inorder array is not sorted. Hence, even a 'BST-looking' tree might need swaps if its inorder sequence isn't sorted numerically.

Case 3: Empty Tree

An empty tree has no nodes, and therefore, no swaps are needed. The base case is handled trivially with a return value of 0.

Case 4: Single Node Tree

A single-node tree is trivially a BST because there's nothing to compare or reorder. It naturally satisfies all BST properties. Thus, the minimum number of swaps is 0.

Case 5: Unbalanced Binary Tree

Unbalanced trees have the same logic applied: get the inorder traversal, sort it, and count the swaps. The shape of the tree doesn't affect the algorithm since only the order of values (not structure) is relevant. Even if the shape is skewed or sparse, the solution depends only on sorting the inorder array and computing the cycle counts.

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.

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

⬅ Previous TopicConvert a Binary Tree into a Sum Tree

Next Topic ⮕Check if a Binary Tree is a Sum Tree