# 23.12.2024 [2471. Minimum Number of Operations to Sort a Binary Tree by Level]

Min swaps to sort tree layers #medium #cycle-sort #bfs

23.12.2024

2471. Minimum Number of Operations to Sort a Binary Tree by Level medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/841

Problem TLDR

Min swaps to sort tree layers #medium #cycle-sort #bfs

Intuition

Can't solve without a hint. The hint: cycle-sort has optimal swaps count.

    // 0 1 2 3 4 5
    // 4 5 1 0 3 2
    // 0     4  
    //   1 5
    //     2     5
    //       3 4

    //
    // 7 6 5 4
    // 0 1 2 3
    // 3 2 1 0

To do the cycle-sort, we convert the layer numbers into indices sorted accordingly, then do swap(ix[i], ix[ix[i]]) until all indices at their places.

Approach

• we can use a hashmap or just an array for indices to value mapping

Complexity

• Time complexity: $$O(nlog(n))$$ to sort layers

• Space complexity: $$O(n)$$

Code

    fun minimumOperations(root: TreeNode?): Int {
        val q = ArrayDeque<TreeNode>(listOf(root ?: return 0))
        var res = 0
        while (q.size > 0) {
            val s = ArrayList<Int>()
            repeat(q.size) {
                val n = q.removeFirst(); s += n.`val`
                n.left?.let { q += it }; n.right?.let { q += it }
            }
            val ix = s.indices.sortedBy { s[it] }.toIntArray()
            for (i in 0..<ix.size) while (ix[i] != i) {
                ix[i] = ix[ix[i]].also { ix[ix[i]] = ix[i] }; res++
            }
        }
        return res
    }

    pub fn minimum_operations(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let Some(r) = root else { return 0 };
        let (mut q, mut r) = (VecDeque::from([r]), 0);
        while q.len() > 0 {
            let mut s = vec![];
            for _ in 0..q.len() {
                let n = q.pop_front().unwrap(); let n = n.borrow(); s.push(n.val);
                if let Some(n) = n.left.clone() { q.push_back(n) }
                if let Some(n) = n.right.clone() { q.push_back(n) }
            }
            let mut ix: Vec<_> = (0..s.len()).collect();
            ix.sort_unstable_by_key(|&i| s[i]);
            for i in 0..ix.len() { while ix[i] != i {
                let t = ix[i]; ix[i] = ix[t]; ix[t] = t; r += 1
            }}
        }; r
    }

    int minimumOperations(TreeNode* root) {
        int r = 0; vector<TreeNode*> q{root};
        while (q.size()) {
            vector<TreeNode*> q1; vector<int> s, ix(q.size());
            for (auto n: q) {
                s.push_back(n->val);
                if (n->left) q1.push_back(n->left);
                if (n->right) q1.push_back(n->right);
            }
            iota(begin(ix), end(ix), 0);
            sort(begin(ix), end(ix), [&](int i, int j){ return s[i] < s[j];});
            for (int i = 0; i < ix.size(); ++i) for (; ix[i] != i; ++r)
                swap(ix[i], ix[ix[i]]);
            swap(q, q1);
        } return r;
    }