431. Convert a BST Into a Balanced BST

Given a binary search tree that may be unbalanced (even fully skewed), rebuild it into a height-balanced BST containing the same values and print it using level-order tokens. Build it with this exact rule on the tree's sorted values: 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. 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 (possibly skewed) BST ('N' marks an absent child). Output: Print the rebuilt balanced BST as space-separated level-order tokens, omitting trailing 'N' tokens.

1 <= number of nodes <= 10^5

This 'extract sorted values, then rebuild from the middle recursively' technique is the exact same core idea as 'build a balanced BST from a sorted array' - recognizing that a BST's inorder gives you that sorted array for free connects the two problems directly.

Rebuild a possibly lopsided binary search tree into a well-balanced one containing the exact same values. Brute force: Repeatedly perform tree rotations to rebalance the existing structure directly (like an AVL tree's rebalancing logic) - this works but is considerably more complex to implement correctly than simply extracting the sorted values and rebuilding from scratch. Optimised: Since a BST's inorder traversal is ALREADY sorted, you get the sorted array 'for free' with no separate sorting step - building a fresh balanced tree from that sorted array using the standard 'always pick the middle element as root' recursive construction directly guarantees balance, far simpler than in-place rotation-based rebalancing.

Collect every node's value using any traversal (preorder or level order works fine), then sort the collected values, and finally build the balanced tree recursively by picking the middle element of the current [lo, hi] range as the root and recursing on the two halves. Sorting is only needed here because the initial collection step didn't assume anything about the tree's structure. This works for any binary tree, not just a BST, which is why it needs an explicit sort step. Time: O(n log n) Space: O(n)

Avoid the auxiliary array altogether using the Day-Stout-Warren technique: first perform a series of right rotations to turn the BST into a fully right-skewed 'vine' (a sorted linked list expressed as tree nodes) in O(n) time using only pointer rotations. Then perform repeated rounds of left rotations over the vine to compress it into a perfectly (or near-perfectly) balanced tree, again in O(n) time. Because every step reuses the existing nodes and only rewires pointers, no separate array of values is ever materialized, so the extra space drops to O(1) (beyond the recursion/output), compared to the O(n) auxiliary array both earlier approaches need. Time: O(n) Space: O(1)

Exploit the BST property directly: an inorder traversal (left, root, right) of a BST visits values in strictly sorted order for free, so there is no need to sort anything afterward. Collect the inorder traversal into an array in O(n) time, then recursively build the balanced tree from that array using the given midpoint rule (root = element at floor((lo+hi)/2), then recurse on the left and right sub-ranges). This removes the O(n log n) sort of the brute-force approach entirely, dropping to linear time. Time: O(n) Space: O(n)

1. Perform an inorder traversal of the original BST - since it's already a valid BST, this traversal is automatically already sorted, with no extra sorting needed. 2. Recursively build a new tree from this sorted array: the root is the middle element (using floor((lo+hi)/2) for the exact tie-breaking rule), the left subtree is built the same way from everything before the middle, and the right subtree from everything after. 3. This 'always pick the middle' rule naturally produces a height-balanced tree.

Time: O(n) - one traversal to extract sorted values, plus one more linear-time pass to rebuild the balanced tree from them. Space: O(n), for the extracted sorted array and the newly built tree.

Test with a fully skewed (linked-list-shaped) input BST, a single-node tree, an already-balanced BST, and a tree with 10^5 nodes for performance.

Be precise about following the EXACT tie-breaking rule given (floor((lo+hi)/2) for the middle index) - different tie-breaking conventions produce different, but equally 'balanced', trees, and matching the expected exact output requires following the stated rule precisely.