Loading problem...
You are given the root of a Binary Search Tree (BST). Your task is to transform this tree into a right-skewed tree (also known as a "vine" or "linked list tree") where:
In essence, you are "flattening" the BST into a single right-leaning chain that preserves the sorted order of the original tree's values. The transformation should reuse the existing nodes rather than creating new ones.
Key Insight: Since the input is a valid BST, an in-order traversal naturally visits nodes in ascending order. Your goal is to restructure the tree so that this in-order sequence becomes the right-child chain of the output tree.
root = [5,3,6,2,4,null,8,1,null,null,null,7,9][1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]The original BST has nodes with values 1 through 9. After reorganization, the tree becomes a right-skewed chain starting from 1 (the smallest) and ending at 9 (the largest). Each node only has a right child pointing to the next larger value, with no left children.
root = [5,1,7][1,null,5,null,7]The BST with nodes 1, 5, and 7 is transformed. Node 1 (smallest) becomes the new root, with 5 as its right child, and 7 as the right child of 5. All left pointers are null.
root = [2,1,3][1,null,2,null,3]A simple 3-node BST is flattened into a right chain: 1 → 2 → 3, maintaining the sorted order from the original in-order traversal.
Constraints