130. Construct a BST From a Preorder Traversal

Given the preorder traversal of a binary search tree (n distinct values, space-separated), reconstruct the tree and print it 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.

Input: A single line of n space-separated distinct integers giving the BST's preorder traversal. Output: Print the reconstructed tree's level-order tokens ('N' for absent children) on one line, omitting any trailing 'N' tokens.

1 <= n <= 10^5, all values distinct

This relies entirely on values within each side's group ALREADY being a valid preorder for that subtree - a direct consequence of preorder always visiting the root before recursing into children, which is exactly what makes the split-and-recurse approach correct.

Given only a BST's preorder traversal, rebuild the actual tree. Brute force: Insert each value one at a time into an initially-empty BST using standard BST insertion rules - this works correctly and is simple, though it can degrade to O(n²) in the worst case (a skewed preorder) without extra care. Optimised: Recognizing that the FIRST value smaller/larger split naturally preserves each side's own valid preorder sub-sequence lets you recursively partition the array directly (rather than inserting one value at a time) - with an efficient partitioning approach (or a bound-based single pass using min/max range checks), this can be done in true O(n) rather than relying on repeated insertions.

Exploit the fact that in a BST preorder, once a value smaller than the current node appears it starts the left subtree, and everything from the first larger value onward belongs to the right subtree. Recursively build the tree by passing each call a valid (min, max) range and only consuming the next preorder value if it falls inside that range, which builds every node in constant time via a single pointer that always advances through the array exactly once. This avoids the pathological repeated re-insertion cost of the brute-force approach entirely, but for a very skewed BST the recursion depth can reach n, risking a stack overflow for large inputs. Time: O(n) Space: O(h)

Start with an empty tree and insert the preorder values one at a time using the standard BST insertion rule (go left if smaller, right if larger, until an empty spot is found). Since preorder values arrive in an order consistent with some valid BST, this always reconstructs the correct tree, but on an already-sorted or nearly-sorted input the tree degenerates into a long chain, making each insertion take time proportional to the number of nodes inserted so far. Time: O(n^2) Space: O(n)

Use the same min/max bounding insight as the recursive approach, but simulate the recursion manually with an explicit stack of (node, upper-bound) pairs instead of relying on language call frames: push the root, and for each subsequent value, pop stack entries whose bound it violates to find its correct parent, attaching it as a left or right child accordingly, then push it back on. This produces the identical tree in the same linear time as the recursive method, but removes any risk of stack overflow from deep recursion, which matters since n can be as large as 10^5 and the preorder could describe a completely skewed tree. Time: O(n) Space: O(n)

1. The FIRST value is always the root. 2. Every SUBSEQUENT value smaller than the root belongs to the left subtree; every value larger belongs to the right subtree - and critically, within each group, the values keep their original relative order, which is ALREADY a valid preorder for that subtree. 3. Recurse on the left group and the right group the same way.

Time: O(n) with an efficient bound-checking single pass (tracking a valid range as you consume the preorder sequence); O(n²) in the worst case with naive repeated BST insertion on a skewed input. Space: O(n) for the constructed tree, plus O(h) for the recursion stack.

Test n=1 (output is just that single value), a strictly increasing sequence (purely right-skewed tree), a strictly decreasing sequence (purely left-skewed tree), and n=10^5 for performance.

Be ready to mention the more advanced O(n) approach (using a valid (low,high) range passed through recursion, consuming the preorder array with a shared index) as an improvement over the O(n²) naive-insertion approach on skewed inputs.