441. Flatten a BST to a Sorted (Right-Skewed) List

Given a binary search tree, rearrange it in place into a right-skewed chain - every node's left child is empty, and following right children visits every value in ascending order - and print the result 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 BST ('N' marks an absent child). Output: Print the flattened right-skewed tree as space-separated level-order tokens, omitting trailing 'N' tokens.

1 <= number of nodes <= 10^5

The output naturally alternates value, N, value, N, ... since the left child is ALWAYS empty for every node in the resulting chain except that the very last node has no trailing N once trailing N's are omitted per the output convention.

Rearrange a BST in place into a single right-leaning chain, where following right children visits every value in ascending order. Brute force: Extract all values via inorder traversal into an array, THEN build a fresh right-skewed chain from scratch using that array, discarding the original tree's nodes entirely - this works but does unnecessary extra allocation when the original nodes can simply be relinked in place. Optimised: Since inorder traversal already visits values in the exact target order, you can relink the EXISTING nodes' right-child pointers as you traverse (rather than building brand new nodes) - achieving the flattening with just one traversal and simple pointer reassignment, no separate array needed if implemented carefully (tracking a 'previous node' reference during the traversal).

Perform an iterative inorder traversal using an explicit stack instead of recursion or a value array: push left children onto the stack, and each time a node is popped (visited in ascending order), immediately detach it from the original tree structure and append it as the next node of a growing right-skewed chain (setting its left pointer to null and linking the previous chain node's right pointer to it). This avoids buffering all values in a separate array, using only the traversal stack as auxiliary space, and reuses the existing nodes directly. Time: O(n) Space: O(h) (stack depth, up to O(n) worst case but O(log n) on average)

Use Morris inorder traversal, which achieves the ascending-order visitation without recursion or an explicit stack: for a node with a left subtree, find its inorder predecessor (rightmost node of the left subtree) and temporarily thread that predecessor's right pointer to the current node, using that thread to return to the current node later and then removing it once used. As each node is visited in ascending order via this threading technique, relink it directly into the growing right-skewed chain (left = null, previous chain node's right = this node). This achieves the same linear-time flattening as the stack-based approach but uses only a constant amount of auxiliary space beyond the tree itself, since the temporary threads are stored in the tree's own pointers. Time: O(n) Space: O(1) extra

Perform a standard inorder traversal of the BST, collecting every node's value into an array in ascending order (guaranteed by the BST property), which takes O(n) time and O(n) extra space. Then discard the shape of the original tree and construct a brand-new right-skewed chain of nodes from that array, where each node's left child is null and its right child is the next node in the array. Print the resulting chain via level order, omitting trailing 'N' tokens. This is correct but relies on a full auxiliary array rather than reusing the existing nodes' pointers as it goes. Time: O(n) Space: O(n)

1. Perform an inorder traversal of the BST - since it's a valid BST, this visits values in ascending order automatically. 2. Build a new chain by linking each visited value's node to the NEXT visited value's node as its right child. 3. Every node's left child is set to empty (null/N) throughout this chain.

Time: O(n) - one single inorder traversal, relinking pointers as you go. Space: O(h) for the recursion stack if done recursively, or O(1) extra if done iteratively with Morris traversal.

Test with a single-node tree, a BST that is already right-skewed, a left-skewed BST, and a tree with 10^5 nodes for performance.

Be ready to mention that this exact 'flatten' operation (BST to sorted linked-list-like structure) is a common intermediate step in solving OTHER problems, like 'BST to sorted doubly linked list' - recognizing that this useful transformation reappears is worth mentioning.