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

Explanation

To solve this problem, we can perform a breadth-first search (BFS) traversal of the binary tree while keeping track of the values at each level. We can then sort the values at each level and calculate the minimum number of operations needed to make them strictly increasing.

Perform a BFS traversal of the binary tree to collect values at each level.
For each level, sort the values and calculate the number of operations needed to make them strictly increasing.
Sum up the operations required for each level to get the total minimum number of operations.

Time complexity: O(n log n) where n is the number of nodes in the binary tree. Space complexity: O(n) where n is the number of nodes in the binary tree.

View Leetcode Problem

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int minOperations(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> levels = new ArrayList<>();

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> levelValues = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                levelValues.add(curr.val);

                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }

            levels.add(levelValues);
        }

        int operations = 0;
        for (List<Integer> level : levels) {
            List<Integer> sortedLevel = new ArrayList<>(level);
            Collections.sort(sortedLevel);
            operations += getOperations(level, sortedLevel);
        }

        return operations;
    }

    private int getOperations(List<Integer> level, List<Integer> sortedLevel) {
        int operations = 0;
        for (int i = 0; i < level.size(); i++) {
            if (!level.get(i).equals(sortedLevel.get(i))) {
                operations++;
            }
        }
        return operations;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

Explanation

Code Editor (Testing phase)

Improve Your Solution