Minimum number of operations to sort a binary tree by level

Tree Breadth-First Search Binary Tree

74.2% acceptance

Feb 27, 2026

1248

You are given the root of a binary tree with unique values. In one operation, you can choose any two nodes at the same level and swap their values. Return the minimum number of operations needed to make the values at each level sorted in a strictly increasing order.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>> }
// impl TreeNode { #[inline] pub fn new(val: i32) -> Self { TreeNode { val, left: None, right: None } } }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn minimum_operations(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut total = 0i32;
    let mut queue = std::collections::VecDeque::new();
    if let Some(r) = root { queue.push_back(r); }
    while !queue.is_empty() {
      let level_size = queue.len();
      let mut vals: Vec<i32> = Vec::with_capacity(level_size);
      for _ in 0..level_size {
        let node = queue.pop_front().unwrap();
        let borrow = node.borrow();
        vals.push(borrow.val);
        if let Some(l) = borrow.left.clone() { queue.push_back(l); }
        if let Some(r) = borrow.right.clone() { queue.push_back(r); }
      }
      // Count minimum swaps to sort vals (cycle decomposition)
      let mut indexed: Vec<(i32, usize)> = vals.iter().copied().enumerate().map(|(i, v)| (v, i)).collect();
      indexed.sort();
      // indexed[i].1 = original position of the i-th smallest element
      let mut target = vec![0usize; vals.len()];
      for (sorted_pos, &(_, orig)) in indexed.iter().enumerate() {
        target[orig] = sorted_pos;
      }
      let mut visited = vec![false; vals.len()];
      let mut swaps = 0i32;
      for i in 0..vals.len() {
        if visited[i] || target[i] == i { visited[i] = true; continue; }
        let mut cycle = 0;
        let mut j = i;
        while !visited[j] {
          visited[j] = true;
          j = target[j];
          cycle += 1;
        }
        swaps += cycle - 1;
      }
      total += swaps;
    }
    total
  }
}