Convert Binary Tree to Binary Search Tree

Problem Given a Binary Tree that is not necessarily a BST, convert it into a Binary Search Tree while preserving the original tree's exact shape — every node keeps its position, only the values move.

Input / Output

• Input: root of an arbitrary binary tree.
• Output: the same tree structure, with values rearranged so the BST property holds at every node.

Constraints

• Up to 10^4 nodes; node values are typically assumed distinct.
• The structure is fixed — no rotations, no re-linking, no rebuilding a balanced tree. Only values may be reassigned.

Example

• Input tree: root 10 with left child 2 and right child 7. In-order traversal visits left, root, right, so the sorted values [2, 7, 10] are written back in that order: left = 2, root = 7, right = 10.
• Tricky case: a fully skewed tree (a chain) still works — the in-order traversal of a right-leaning chain is top-to-bottom, so the sorted values are written down the chain in ascending order.