413. Minimum Swaps to Convert a Binary Tree Into a BST

Given a binary tree with distinct values, find the minimum number of node-value swaps needed so that the tree becomes a valid binary search tree, and print that count. Swapping two nodes means swapping their values; the tree's shape never changes. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: A single line of space-separated level-order tokens ('N' for missing children) describing a binary tree whose values are all distinct. Output: Print a single integer - the minimum number of value swaps needed to make the tree's inorder traversal sorted.

1 <= number of nodes <= 10^5, all values distinct

The tree's SHAPE never changes throughout this whole process - only VALUES move between existing node positions - which is exactly why the inorder traversal (a fixed sequence of positions) is the right lens to reduce this to a pure array-sorting problem.

Given a binary tree's fixed shape, find the fewest value-swaps needed so its inorder traversal becomes sorted (making it a valid BST). Brute force: Try every possible sequence of swaps directly, searching for the shortest one that sorts the inorder sequence - this branches combinatorially and is impractical to search directly. Optimised: Reducing the problem to 'minimum swaps to sort an array' (via the tree's inorder traversal) lets you reuse the well-known cycle-detection technique: build a mapping from each value's CURRENT position to its TARGET (sorted) position, and every cycle in this mapping of length L requires exactly L-1 swaps to resolve - summing over all such cycles gives the true minimum, with no need to search through swap sequences directly.

Take the inorder traversal, pair each value with its original index, and sort these pairs by value to know the target position for every element in O(n log n). Then actually perform the necessary swaps on the array to realize this sorted order, maintaining a hashmap from value to its current position so that, whenever position i doesn't yet hold its correct value, the element that does belong there can be located and swapped in O(1) instead of scanned for, counting each swap performed. This still touches every out-of-place cycle explicitly, which does the same essential work as computing the answer directly but with the overhead of simulating the actual data movement. Time: O(n log n) Space: O(n)

Take the inorder traversal, pair each value with its original index, and sort the pairs by value in O(n log n) to know where every element ultimately needs to go. Then, using a visited array, walk through and find cycles in this position-mapping permutation without performing any actual swaps at all: for a cycle of length L, exactly L-1 swaps are needed to fix it, so the answer is simply the sum of (cycle length - 1) over all cycles. This computes the exact minimum swap count in one linear pass after sorting, with no simulated data movement or extra hashmap lookups, making it the cleanest and most memory-efficient version of the algorithm. Time: O(n log n) Space: O(n)

First take the inorder traversal of the tree, which for a BST would appear in sorted order - so the number of swaps needed to make the tree a valid BST equals the number of swaps needed to sort this inorder sequence. Simulate this directly with a selection-sort-style process: repeatedly scan the remaining unsorted portion of the array to find the position of the value that belongs at the current front position, swap it into place, and count the swap. Because finding each correct element requires a full linear scan of the remaining array, this takes quadratic time overall despite computing the exact right answer. Time: O(n^2) Space: O(n)

1. Realize that since the SHAPE never changes, the only thing that must become sorted is the tree's INORDER traversal sequence - a tree is a valid BST exactly when its inorder sequence is ascending. 2. This reduces directly to the classic 'minimum swaps to sort an array' problem, applied to the collected inorder values. 3. Solve that with cycle detection: map each value to where it SHOULD be in sorted order, then for every cycle of length L in this mapping, exactly L-1 swaps are needed - sum this across all cycles.

Time: O(n log n) - dominated by sorting the inorder values (or the equivalent index-mapping construction); the cycle-detection itself is O(n). Space: O(n), for the inorder-traversal array and the value-to-target-position mapping.

Test a tree that's already a valid BST (answer 0), a single-node tree, an inorder sequence that is fully reversed, and n=10^5 nodes for performance.

Be ready to explain the cycle-detection technique for 'minimum swaps to sort an array' from first principles (a common standalone interview question in its own right) - this problem is really testing whether you can recognize that the tree structure reduces cleanly to that simpler, more familiar array problem.