279. Convert a BST to a Min-Heap

Given a binary search tree, convert it into a min-heap while preserving the tree's exact shape (no node is added, removed, or relocated) - only the values are redistributed among the existing nodes. Because this can be done in more than one way, produce it with this exact construction so the answer is unique: read out every value via an in-order traversal of the BST (which comes out already sorted ascending, since it's a BST), then write those sorted values back into the tree one at a time following a preorder traversal (visit a node, then its whole left subtree, then its whole right subtree), assigning the next-smallest unused value to each node as you visit it. Print the resulting tree's level order (using the same convention as the input). 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 contains the BST's space-separated level-order tokens, where 'N' denotes a missing node: the first token is the root, and then for each node dequeued in level order its left-child token then its right-child token follows (missing trailing tokens count as N). Output: Print the resulting min-heap tree's level order, using that same token convention.

1 <= number of nodes <= 10^5

This is conceptually the mirror of 'Convert a Binary Tree Into a BST' (which uses INORDER for reassignment, since a BST needs ascending order when read inorder) - recognizing which traversal order matches which target property is the key skill both problems test.

Given a BST, redistribute its existing values (without changing the tree's shape at all) so it becomes a valid min-heap. Brute force: Try every possible way of assigning the sorted values to the existing nodes and check which assignment produces a valid min-heap - this is combinatorially wasteful when the direct 'sorted values in preorder order' assignment is guaranteed correct. Optimised: Since preorder guarantees every node is visited BEFORE its descendants, handing out values in ASCENDING order during a preorder pass guarantees each node's value is smaller than everything beneath it by construction - no validation step needed afterward, unlike a trial-and-error assignment.

Exploit the BST property directly: an inorder traversal (left, node, right) of a BST visits values in already-sorted order, so simply collecting values this way avoids any explicit sort. Store the sorted values in an array with an index pointer, then do a recursive preorder traversal (node, left subtree, right subtree) that assigns arr[pointer++] to each node's value as it is visited, exactly matching the problem's required construction. This drops the log n sorting factor but still relies on recursion for both traversals, whose call stack can grow as large as the tree itself. Time: O(n) Space: O(n)

Perform the inorder collection using Morris traversal, which temporarily threads the tree via the predecessor's right pointer to visit nodes in sorted order without any recursion or explicit stack, and then perform the preorder assignment using an explicit iterative stack instead of recursive calls. The asymptotic time stays the same, but this avoids the O(n)-deep call stack that recursion would need on a skewed tree of up to 10^5 nodes, which risks a stack overflow that the iterative/Morris version sidesteps entirely. Time: O(n) Space: O(n)

Collect every node's value via any traversal into a list, then explicitly sort that list with a general comparison sort even though the input is already a BST. Afterward, do a preorder traversal of the tree, assigning the next unused value from the sorted list to each node as it is visited. This produces the exact construction required by the problem, but redundantly pays an O(log n) sorting factor on data that was already guaranteed sorted by the BST property. Time: O(n log n) Space: O(n)

1. Collect every value via an INORDER traversal of the BST - since it's a valid BST, this comes out already sorted ascending. 2. Do a SECOND pass, this time in PREORDER (visit node, then left subtree, then right subtree), assigning the next-smallest unused value (from the front of the sorted list collected in step 1) to each node as you visit it. 3. Since preorder always visits a node strictly before any of its descendants, and values are handed out in ascending order, every node necessarily gets a SMALLER value than everything beneath it - exactly the min-heap property.

Time: O(n) - one inorder pass to collect sorted values, one preorder pass to reassign them. Space: O(n), for the collected sorted values array, plus O(h) for the recursion stack.

a single-node tree, and a completely skewed (linked-list-shaped) BST with up to 10^5 nodes, whose preorder visiting order differs greatly from a balanced tree's.

Be ready to explain clearly WHY preorder (specifically, not inorder or postorder) is the correct traversal order for reassignment - preorder's 'parent before children' visiting guarantee is exactly what the min-heap property (parent smaller than children) needs.