Find minimum swaps required to convert a Binary tree into BST

The problem, simply

You get a binary tree with different numbers. In one swap you may pick any two nodes and trade their numbers. The shape of the tree never changes.

Find the smallest number of swaps that turns it into a binary search tree: a tree where, for every node, everything on its left is smaller and everything on its right is bigger.

The tree often comes as an array of a complete tree, where node i has children 2i + 1 and 2i + 2.

A story to remember it

Picture it

Examples

Way 1: the simple way

Read the tree into a list with an inorder walk. Then do a selection sort on the list and count the swaps: for each spot, find the smallest number in the rest, and swap it in if it is not there yet.

Selection sort happens to use the fewest swaps possible, because every swap puts at least one number in its final spot and finishes a loop as soon as it can. It is only slow at finding the smallest each time.

1. Inorder walk into a.
2. For i from 0: find the smallest in a[i..]. If it is not at i, swap and count.

import java.util.*;

class Solution {
    public int minSwaps(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int[] a = list.stream().mapToInt(Integer::intValue).toArray();
        int swaps = 0;
        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;
            if (min != i) {                          // not in its seat yet
                int t = a[i]; a[i] = a[min]; a[min] = t;
                swaps++;
            }
        }
        return swaps;
    }

    private void inorder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }
}

How long it takes: the inorder walk is O(n), but the selection sort scans the rest of the list for every spot, O(n^2). Extra room: the list, O(n).

Way 2: the clever way

Do not sort by swapping. Count the loops instead.

1. Inorder walk into a.
2. Sort a copy to learn where each number must end up (its "seat").
3. Go through the spots. From an unvisited spot, follow "this number wants that seat" until you come back, marking spots as visited. That is one loop of size L.
4. Add L - 1 for each loop.

import java.util.*;

class Solution {
    public int minSwaps(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int n = list.size();
        Integer[] order = new Integer[n];                // spots, sorted by the number in them
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (x, y) -> Integer.compare(list.get(x), list.get(y)));
        // order[s] = the spot where the number that belongs in seat s sits now
        boolean[] seen = new boolean[n];
        int swaps = 0;
        for (int s = 0; s < n; s++) {
            if (seen[s] || order[s] == s) continue;      // done, or already in its seat
            int size = 0;
            for (int j = s; !seen[j]; j = order[j]) {    // walk around the loop
                seen[j] = true;
                size++;
            }
            swaps += size - 1;                           // a loop of size L needs L - 1 swaps
        }
        return swaps;
    }

    private void inorder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }
}

How long it takes: the sort is O(n log n), the loop walk is O(n) because each spot is visited once. Total O(n log n). Extra room: the list, the order and the seen marks, O(n).

Watch out for

• You may swap values only, not move nodes. So the shape stays, and the inorder spots stay the same. That is why it is a pure array problem after the walk.
• The values must be different. With repeats, "the seat" of a number is not unique, and the problem changes.
• For the array form, do the inorder walk on indices: go to 2i + 1, write a[i], go to 2i + 2, stopping when the index is past the end.

What interviewers ask next

• Minimum swaps to sort any array: exactly Way 2 without the tree. This is the real interview question hiding inside.
• Only swaps of neighbours are allowed. Then the answer is the number of inversions, which merge sort can count in O(n log n).
• Turn a tree into a search tree while keeping its shape (not counting swaps). Inorder walk, sort the values, then write them back in a second inorder walk.
• Why is L - 1 the best for a loop? Each swap can split one loop into two. You start with some number of loops and need n loops of size 1, so you need at least n - loops swaps, and the method above uses exactly that many.

Remember this

Grown-up words: reading left to right is an inorder traversal, the seats are the positions in sorted order, the loops are the cycles of a permutation, and the answer is n minus the number of cycles.