2471.minimum-number-of-operations-to-sort-a-binary-tree-by-level.md

2471. Minimum Number of Operations to Sort a Binary Tree by Level

BFS + Cycle Sort

• We use BFS to traverse the tree level by level.
• We use cycle sort to sort the values in each level.
• We count the number of swaps to sort the values in each level.
• We return the total number of swaps.

// Original order
index 0, 1, 2, 3
value 7, 6, 8, 5

// After sorting
index 0, 1, 2, 3
value 5, 6, 7, 8

// Start cycle sort
index 0, 1, 2, 3
value 7, 6, 8, 5
      i // see 7, should place at index 2, swap 7 and 8
value 8, 6, 7, 5
      i // see 8, should place at index 3, swap 8 and 5
value 5, 6, 7, 8
      i // see 5, it's in the correct position, move to next index

fun minimumOperations(root: TreeNode?): Int {
    if (root == null) return 0
    val queue = ArrayDeque<TreeNode>()
    queue.addLast(root)
    var swap = 0
    while (queue.isNotEmpty()) {
        val size = queue.size
        val values = mutableListOf<Int>()
        for (i in 0 until size) {
            val node = queue.removeFirst()
            values.add(node.`val`)

            if (node.left != null) {
                queue.addLast(node.left)
            }
            if (node.right != null) {
                queue.addLast(node.right)
            }
        }
        swap += calculateSwapCount(values)
    }
    return swap
}

// We count the number of swaps to sort by cycle sort.
private fun calculateSwapCount(values: MutableList<Int>): Int {
    var count = 0
    val sortedValues = values.sorted()
    val valueIndex = HashMap<Int, Int>()
    for (i in sortedValues.indices) {
        valueIndex[sortedValues[i]] = i
    }
    var i = 0
    while (i < values.size) {
        val correctIndex = valueIndex[values[i]]!!
        if (values[i] != values[correctIndex]) {
            values.swap(i, correctIndex)
            count++
        } else {
            i++
        }
    }
    return count
}

private fun MutableList<Int>.swap(i: Int, j: Int) {
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}

• Time Complexity: O(n * width), where n is the number of nodes in the tree, width is the maximum width of the tree.
• Space Complexity: O(n), where n is the number of nodes in the tree.