Java || 15ms 100% || BFS, Sort, Un-sort || Explanations, FAST!!!
--- General description of code ---\n\nThe code below determines how many pair-swaps would be needed for the nodes within each level of a tree to become sorted 
**--- General description of code ---**\n\nThe code below determines how many pair-swaps would be needed for the nodes within each level of a tree to become sorted into ascending numerical order.  The code does this by using a **Breadth First Search (BFS)** to do a level order traversal of the tree.  The BFS processes the levels of the tree one at a time.\n\nFor each level of the tree, the node.val values from the nodes, are copied into a `long[]` array, along with the node\'s left-to-right positional index (0..n) across the tree level.  The `long[]` array is sorted into ascending order.  The sorted `long[]` array is then "**un**sorted", using swapping of pairs, to re-create the original unsorted array.  The number of swaps to unsort the array, is also the number of swaps that would have been needed to sort the array.\n\nFixed length arrays work well to sort the node values on a level of the tree, because we already know the number of nodes on that level of the tree, so the array length can be correctly allocated. Also, sorting and accessing arrays of primitive types, is faster than using more complex data structures such as List class objects, or arrays of objects such as Pair.\n\nThe values in the `long[]` array contain both the node.val value from each node, and the original index in the array before the array was sorted.  The original index is also the index position of the node across the level of the tree.  When the nodes in the `long[]` array are sorted, each `long` in the array will preserve the index it originally came from.  For the un-sorting process by swaps, this index will allow us to restore each `long` value to its original position in the array.\n\nThe algorithm to **un-sort** the nodes of the array is:\n\n1. Begin a loop through each index `i` in the sorted array `arr`.\n2. If index `i` is past the end of array `arr`, then done.\n3. Set `j` to be the original un-sorted index of the value in `arr[i]`.\n3. If `i==j` then `arr[i]` is already in its original unsorted position, so assign i=i+1 and go back to step #2.\n4. The value in `arr[i]` is not in its original position, so swap the values in `arr[i]` and `arr[j]`, which moves the value in `arr[i]` to its original un-sorted position within array `arr`.\n5. Keep `i` as the same index value. Because we have previously swapped a new value into `arr[i]`, that value may also need to be moved to its original un-sorted position.  So go back to step #2.\n\nWithin each value of the `long[]` array, the low 20 bits store the original un-sorted index into the `long[]` array.  The next higher 17 bits contain the node.val value form the node.  The complication of packing these two values into a single `long` was done to gain execution speed from working with arrays of primitive data types.\n\n**--- Four versions of code ---**\n\nThe four versions of code further below have titles and, as of August 2023, fastest runtimes:\n\n*  Uncommented - Simpler and best-practices.  (20ms)\n*  Uncommented - Speed optimized.  (15ms)\n*  Commented - Simpler and best-practices.  (20ms)\n*  Commented - Speed optimized.  (15ms)\n\nThe difference between the "simpler and best-practices" and the "speed optimized" is how the Breadth First Search (BFS) list of nodes on a level are stored for level-order traversal of the tree.  \n\nIn the "**simpler and best-practices**" code, the BFS list of nodes is implemented as LinkedList.  The LinkedList can handle future leetcode problem constraint changes, such as larger tree sizes.  The LinkedList also allow the code to be simpler, and simpler code is less likely to have bugs.\n\nIn the "**speed optimized**" code, the BFS list is implemented as fixed length arrays that are staticly allocated.  The fixed length arrays produce a "subscript out of bounds" error if the leetcode problem constraints are changed to allow larger trees.  The arrays are also statically allocated, which gains speed because the large maximum-required-length arrays are only created and allocated once for multiple leetcode test cases, instead of non-static arrays that would be re-allocated for each leetcode test case.  The static arrays are also NOT thread-safe.  A feature of Java\'s static arrays that is not used in the code below, is that static arrays can preserve values and data between leetcode test cases, which can be useful, or can cause difficult to diagnose bugs.\n\nSpeed optimized code may be needed to meet a job\'s requirements, especially for real-time programming where hardware can force timing requirements on the software.  To meet the speed requirements, bad programming practices can help squeeze more speed from the code, as in the "speed optimized" version of the code below.\n\n**If useful, please upvote.**\n\n**--- Code: Uncommented - Simpler and best-practices (22ms) ---**\n```\nclass Solution {\n    static final int SHIFT = 20;\n    static final int MASK = 0xFFFFF;\n    \n    public int minimumOperations(TreeNode root) {\n        LinkedList<TreeNode> bfsList = new LinkedList();\n        bfsList.addLast(root);\n        int swapCount = 0;\n        \n        while (!bfsList.isEmpty()) {\n            int nodeCount = bfsList.size();\n            long[] sortedNodes = new long[nodeCount];\n            for (int i = 0; i < nodeCount; i++) {\n                TreeNode node = bfsList.pollFirst();\n                sortedNodes[i] = ((long)node.val << SHIFT) + i;\n                if (node.left != null)  bfsList.addLast(node.left);\n                if (node.right != null)  bfsList.addLast(node.right);\n            }\n\n            Arrays.sort(sortedNodes);\n            for (int i = 0; i < nodeCount; i++) {\n                int origIdx = (int)(sortedNodes[i] & MASK);\n                if (origIdx != i) {\n                    long temp = sortedNodes[i];\n                    sortedNodes[i--] = sortedNodes[origIdx];\n                    sortedNodes[origIdx] = temp;\n                    swapCount++;\n                }\n            }\n        }\n        \n        return swapCount;\n    }\n}\n```\n**--- Code: Uncommented - Speed optimized (19ms) ---**\n```\nclass Solution {\n    static final int SHIFT = 20;\n    static final int MASK = 0xFFFFF;\n\n    static final int MAX_NODES_PER_LEVEL = 34465;\n    static final TreeNode[] bfsList1 = new TreeNode[MAX_NODES_PER_LEVEL];\n    static final TreeNode[] bfsList2 = new TreeNode[MAX_NODES_PER_LEVEL];\n\n    \n    public int minimumOperations(TreeNode root) {\n        TreeNode[] curBFS = bfsList1;\n        TreeNode[] nextBFS = bfsList2;\n        int curBFSCount = 0;\n        int nextBFSCount = 0;\n        curBFS[curBFSCount++] = root;\n\n        int swapCount = 0;\n        \n        while (curBFSCount > 0) {\n            long[] sortedNodes = new long[curBFSCount];\n            for (int i = 0; i < curBFSCount; i++) {\n                TreeNode node = curBFS[i];\n                sortedNodes[i] = ((long)node.val << SHIFT) + i;\n                if (node.left != null)  nextBFS[nextBFSCount++] = node.left;\n                if (node.right != null)  nextBFS[nextBFSCount++] = node.right;\n            }\n\n            Arrays.sort(sortedNodes);\n            for (int i = 0; i < curBFSCount; i++) {\n                int origIdx = (int)(sortedNodes[i] & MASK);\n                if (origIdx != i) {\n                    long temp = sortedNodes[i];\n                    sortedNodes[i--] = sortedNodes[origIdx];\n                    sortedNodes[origIdx] = temp;\n                    swapCount++;\n                }\n            }\n            \n            TreeNode[] temp = curBFS;\n            curBFS = nextBFS;\n            nextBFS = temp;\n            curBFSCount = nextBFSCount;\n            nextBFSCount = 0;\n        }\n        \n        return swapCount;\n    }\n}\n```\n**--- Code: Commented - Simpler and best-practices (22ms) ---**\n```\nclass Solution {\n    // Constants used to build values in long[] arrays, where the \n    // each long value contains a node.val from a node, and the \n    // index of that node within the current level of the Breadth-\n    // First-Search (BFS) traversal of the tree.  For eaxmple, if \n    // a node was the third node from the left on its tree level \n    // (at index 2 on the tree level), and the long value built \n    // for sorting the nodes on that level, would be: \n    //      (node.val << SHIFT) + 2\n    // where the "2" is the index position of the third node on \n    // the current level of the tree.  The MASK constant is used \n    // to retrieve the index value out of the long value.\n    static final int SHIFT = 20;\n    static final int MASK = 0xFFFFF;\n    \n    public int minimumOperations(TreeNode root) {\n        LinkedList<TreeNode> bfsList = new LinkedList();\n        bfsList.addLast(root);\n        int swapCount = 0;\n        \n        // Loop through each level of the tree, until no more levels.\n        while (!bfsList.isEmpty()) {\n            // Number of nodes on current level of the BFS level order \n            // traversal of the tree.  Process this many nodes from the \n            // BFS list, then any remaining nodes in the BFS list will \n            // be for the next level of the tree.\n            int nodeCount = bfsList.size();\n            // The nodes of the current tree level, sorted by each node\'s \n            // node.val.  After sorting, this array will tell us where \n            // the final position of each node should be.  The long \n            // values in this array contain the original index that this \n            // node came from for the nodes of this level of the tree.\n            long[] sortedNodes = new long[nodeCount];\n            // Loop through all nodes on this level of the tree.  Obtain \n            // the nodes from the BFS list, which will remove the current \n            // tree level\'s nodes from the list.  While processing the \n            // current tree level\'s nodes, build the next tree level\'s \n            // BFS list by adding the next levels nodes to the end of the \n            // BFS list to be used next time through the `while` loop.\n            // For the current tree level, save the node.val values in \n            // an array, so we can sort the arrays by node.val values.\n            for (int i = 0; i < nodeCount; i++) {\n                TreeNode node = bfsList.pollFirst();\n                sortedNodes[i] = ((long)node.val << SHIFT) + i;\n                if (node.left != null)  bfsList.addLast(node.left);\n                if (node.right != null)  bfsList.addLast(node.right);\n            }\n\n            // For the current tree level, loop through the array of \n            // sorted nodes.  Modify the sorted array to try to \n            // reconstruct the tree level\'s original node order, by \n            // using a series of swaps of node pairs.  The number of \n            // swaps needed to convert the sorted array back to the \n            // original tree node order, is the same number of swaps \n            // that would have been needed to sort the tree nodes to \n            // ascending order.\n            Arrays.sort(sortedNodes);\n            for (int i = 0; i < nodeCount; i++) {\n                int origIdx = (int)(sortedNodes[i] & MASK);\n                if (origIdx != i) {\n                    long temp = sortedNodes[i];\n                    sortedNodes[i--] = sortedNodes[origIdx];\n                    sortedNodes[origIdx] = temp;\n                    swapCount++;\n                }\n            }\n        }\n        \n        return swapCount;\n    }\n}\n```\n**--- Code: Commented - Speed optimized (19ms) ---**\n```\nclass Solution {\n    // Constants used to build values in long[] arrays, where the \n    // each long value contains a node.val from a node, and the \n    // index of that node within the current level of the Breadth-\n    // First-Search (BFS) traversal of the tree.  For eaxmple, if \n    // a node was the third node from the left on its tree level \n    // (at index 2 on the tree level), and the long value built \n    // for sorting the nodes on that level, would be: \n    //      (node.val << SHIFT) + 2\n    // where the "2" is the index position of the third node on \n    // the current level of the tree.  The MASK constant is used \n    // to retrieve the index value out of the long value.\n    static final int SHIFT = 20;\n    static final int MASK = 0xFFFFF;\n\n    // Maximum possible number of nodes in any level of a tree:\n    //    x = 2^(floor(log2(max_total_nodes_in_a_tree)))\n    //    MAX_NODES_PER_LEVEL = max(x, max_total_nodes_in_a_tree - x + 1)\n    static final int MAX_NODES_PER_LEVEL = 34465;\n    // Breadth first search lists that save the nodes from a \n    // single level of the tree.  One list has the nodes of the \n    // current level, and the other list has the nodes of the \n    // next level.  We reference these arrays through the \n    // variables \'curBFS\' and \'nextBFS\', which allows us to \n    // alternate which of the bfsList1 and bfsList2 variables \n    // are current and next levels.\n    static final TreeNode[] bfsList1 = new TreeNode[MAX_NODES_PER_LEVEL];\n    static final TreeNode[] bfsList2 = new TreeNode[MAX_NODES_PER_LEVEL];\n\n    \n    public int minimumOperations(TreeNode root) {\n        // Variables for the Breadth-First-Search (BFS) lists of \n        // nodes, for level-order traversing the of the tree.  \n        // The nodes for each tree level are stored in a current level \n        // array, and a next level array.\n        TreeNode[] curBFS = bfsList1;\n        TreeNode[] nextBFS = bfsList2;\n        int curBFSCount = 0;\n        int nextBFSCount = 0;\n        curBFS[curBFSCount++] = root;\n\n        int swapCount = 0;\n        \n        // Loop through each level of the tree, until no more levels.\n        while (curBFSCount > 0) {\n            // The nodes of the current tree level, sorted by each node\'s \n            // node.val.  After sorting, this array will tell us where \n            // the final position of each node should be.  The long \n            // values in this array contain the original index that this \n            // node came from for the nodes of this level of the tree.\n            long[] sortedNodes = new long[curBFSCount];\n            // Loop through all nodes on this level of the tree.  Obtain \n            // the nodes from the BFS list.  While processing the \n            // current tree level\'s nodes, build the next tree level\'s \n            // BFS list.  For the current tree level, save the node.val \n            // values in an array, so we can sort the arrays by \n            // node.val values.\n            for (int i = 0; i < curBFSCount; i++) {\n                TreeNode node = curBFS[i];\n                sortedNodes[i] = ((long)node.val << SHIFT) + i;\n                if (node.left != null)  nextBFS[nextBFSCount++] = node.left;\n                if (node.right != null)  nextBFS[nextBFSCount++] = node.right;\n            }\n\n            // For the current tree level, loop through the array of \n            // sorted nodes.  Modify the sorted array to try to \n            // reconstruct the tree level\'s original node order, by \n            // using a series of swaps of node pairs.  The number of \n            // swaps needed to convert the sorted array back to the \n            // original tree node order, is the same number of swaps \n            // that would have been needed to sort the tree nodes to \n            // ascending order.\n            Arrays.sort(sortedNodes);\n            for (int i = 0; i < curBFSCount; i++) {\n                int origIdx = (int)(sortedNodes[i] & MASK);\n                if (origIdx != i) {\n                    long temp = sortedNodes[i];\n                    sortedNodes[i--] = sortedNodes[origIdx];\n                    sortedNodes[origIdx] = temp;\n                    swapCount++;\n                }\n            }\n            \n            // Make the next BFS list the current BFS list, for \n            // the next time through the \'while\' loop.\n            TreeNode[] temp = curBFS;\n            curBFS = nextBFS;\n            nextBFS = temp;\n            curBFSCount = nextBFSCount;\n            nextBFSCount = 0;\n        }\n        \n        return swapCount;\n    }\n}\n```\n\n
['Java']