430. Convert a Binary Tree Into a BST

Given an arbitrary binary tree with distinct values (not necessarily a valid BST), reassign its node values - keeping the exact same shape - so that it becomes a valid binary search tree. Print the resulting tree using level-order tokens. Print the resulting tree the same way (level order, 'N' for absent children), but omit any trailing 'N' tokens at the very end of your output. 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 describing the binary tree ('N' marks an absent child); all values are distinct. Output: Print the resulting BST as space-separated level-order tokens, omitting trailing 'N' tokens.

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

This is essentially the SAME core technique as 'Convert a BST into a Balanced BST', just applied to a plain binary tree instead - both rely on the fact that a sorted sequence assigned via inorder traversal produces valid BST ordering, regardless of the tree's actual shape.

Given a binary tree's shape, reassign its values (without changing which nodes connect to which) so it becomes a valid binary search tree. Brute force: Try every possible way of assigning the sorted values to the tree's nodes and check which assignment produces a valid BST - this is combinatorially wasteful when a single, direct inorder-based assignment is guaranteed correct. Optimised: Since a BST is DEFINED by having an ascending inorder traversal, directly writing the sorted values back into the tree in inorder visiting order guarantees the BST property holds by construction - no trial and error, no validation step needed afterward, just two clean traversal passes.

Use the same collect-sort-reassign strategy as the better approach, but perform the two in-order traversals (collection and reassignment) using Morris traversal, which temporarily creates and removes threaded links within the tree itself to simulate an in-order walk without recursion or an explicit stack. The sort still dominates the time complexity, but this removes the O(h) recursion-stack (or explicit stack) overhead of the traversal steps entirely, so the only significant auxiliary memory needed is the O(n) array of values that must be sorted, which is unavoidable for this problem. Time: O(n log n) Space: O(n) for the value array, O(1) auxiliary traversal space

Traverse the tree once (in any order) to collect all n values into an array, sort that array in ascending order using a standard O(n log n) comparison sort, then traverse the tree a second time in in-order and assign the sorted values one by one (using a simple index pointer) to each node as it's visited. This works because an in-order traversal visits nodes in the exact relative order a BST requires, so handing out pre-sorted values in that traversal order automatically produces a valid BST with the same shape, and it's a large improvement over the brute-force approach's repeated scans for the minimum. Time: O(n log n) Space: O(n)

First collect all n node values into an array via any traversal. Then perform an in-order traversal of the tree (the order in which nodes must receive ascending values for the shape to become a valid BST), and for each node visited, scan through the remaining unassigned values in the array to find and remove the current smallest one, assigning it to that node. This is correct because in-order traversal position determines each node's required rank, but repeatedly scanning for the current minimum for every one of the n nodes makes it quadratic. Time: O(n^2) Space: O(n)

1. Collect every node's current value via any traversal, then sort these values. 2. Perform an INORDER traversal of the ORIGINAL tree's shape, and as you visit each node (in inorder order), assign it the next value from the sorted list, in ascending order. 3. Since a BST's defining property is exactly 'inorder traversal is ascending', assigning sorted values in inorder visiting order guarantees the result is a valid BST with the exact same shape.

Time: O(n log n), dominated by sorting the collected values - both traversal passes themselves are O(n). Space: O(n), for the collected and sorted values array.

Test with a single-node tree, a tree that happens to already be a valid BST, a fully skewed tree, and a tree with 10^5 nodes for performance.

Be ready to state clearly WHY this technique is guaranteed correct (a BST's inorder traversal being ascending is a necessary AND sufficient condition) - this elegant guarantee is exactly what removes any need for extra validation afterward.