131. Convert a Sorted Array Into a Height-Balanced BST

Given a sorted array of n distinct integers, build a height-balanced BST from it and print it using level-order tokens. Build it with this exact rule: for the current sub-range [lo, hi] (0-indexed, inclusive), the root is the element at index floor((lo+hi)/2), the left subtree is built the same way from [lo, mid-1], and the right subtree from [mid+1, hi]. 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: The first line contains an integer n. The second line contains n space-separated distinct integers already sorted in ascending order. Output: Print the constructed tree's level-order tokens ('N' for absent children) on one line, omitting trailing 'N' tokens.

1 <= n <= 10^5

This exact 'sorted array to balanced BST' technique is the same core building block reused in 'Convert a BST into a Balanced BST' (which first extracts a sorted array via inorder traversal, then applies this exact same middle-picking construction).

Given a sorted array, build a height-balanced binary search tree containing exactly those values. Brute force: Insert every array value one at a time into an initially-empty BST using standard insertion - this can produce a badly UNBALANCED tree (e.g. a fully skewed chain) if inserted in already-sorted order without any special handling, defeating the entire purpose of the problem. Optimised: Directly picking the MIDDLE element as the root at every recursive level guarantees near-equal-sized left and right subtrees throughout, which is precisely the definition of height-balance - this direct 'divide at the middle' construction is far simpler and more reliable than inserting values one at a time and hoping for balance.

Build the tree recursively following the required rule, but implement each recursive call by physically slicing out new left and right sub-arrays (e.g. copying the elements into brand-new arrays) rather than working with index bounds into the original array. This produces the correct tree since the same root-selection rule is followed at every level, but repeatedly copying sub-array contents across all levels of recursion adds an extra logarithmic factor of wasted copying work and memory. Time: O(n log n) Space: O(n log n)

Build the tree recursively using only (lo, hi) index bounds into the original array instead of copying sub-arrays: compute mid = floor((lo+hi)/2), make it the root, and recurse on (lo, mid-1) and (mid+1, hi). Every array element is looked at exactly once across the whole recursion, since no sub-array is ever duplicated, which removes the extra copying overhead of the brute-force approach while producing the exact same tree shape. Time: O(n) Space: O(n) for the output tree, O(log n) recursion

Simulate the same (lo, hi, mid) recursive construction rule iteratively, using an explicit stack of pending (lo, hi, parent, side) ranges instead of language-level recursion. This produces an identical tree to the recursive version but removes any dependency on the call stack entirely, which is a meaningful practical safeguard here since n can be up to 10^5 and a purely recursive implementation risks a stack overflow on some runtimes even though the tree itself stays balanced. Time: O(n) Space: O(n)

1. Pick the MIDDLE element of the current sub-range (using floor((lo+hi)/2) for the exact tie-breaking rule) as the root. 2. Recursively build the left subtree from everything before the middle, and the right subtree from everything after. 3. This 'always split at the middle' rule naturally keeps both sides close to equal size at every level, guaranteeing a height-balanced result.

Time: O(n) - each element is placed into the tree exactly once across the whole recursive construction. Space: O(n) for the resulting tree, plus O(log n) for the recursion stack (since the recursion depth matches the balanced tree's height).

Test n=1 (single-node tree), an even-length array (checks the floor((lo+hi)/2) lower-middle tie-break is followed exactly), and n=10^5 for performance.

Be precise about following the EXACT tie-breaking convention given (floor((lo+hi)/2)) - a different but equally 'balanced' convention (like ceiling instead of floor) would produce a differently-shaped, still-valid tree that wouldn't match this problem's specific expected output.