Description
Given the root of a Binary Search Tree (BST), rearrange it into an 'increasing order tree' where the leftmost (smallest) node becomes the new root, and every node has no left child and only one right child. A Binary Search Tree has the property that for any node: all values in its left subtree are smaller, and all values in its right subtree are larger. Perform an in-order traversal (left → node → right) to visit nodes in ascending order, then construct a right-skewed tree from those values.
Examples
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]In-order traversal visits nodes as: 1,2,3,4,5,6,7,8,9. The result is a right-skewed tree with these values in order.
root = [4,2,6,1,3,5,7][1,null,2,null,3,null,4,null,5,null,6,null,7]This perfect binary search tree gets flattened by performing in-order traversal (1,2,3,4,5,6,7) and creating a right-skewed tree where each node only has a right child, maintaining the sorted order.
root = [10,5,15,null,7,12][5,null,7,null,10,null,12,null,15]This unbalanced BST with missing left child of node 5 demonstrates that the algorithm works regardless of tree structure. In-order traversal gives (5,7,10,12,15) which becomes the right-skewed result.
Constraints
- •
1 ≤ nodes ≤ 100