Binary Tree to BST Conversion
Filed under Accolite
Free read 2 of 3Perform an inorder traversal to extract all node values into an array.
The question
Given a binary tree, convert it to a Binary Search Tree (BST) such that the original spatial structure of the tree is preserved.
Constraints
- 1 <= number of nodes <= 1000
- -10^4 <= Node.val <= 10^4
Examples
- Input
- root = [10, 2, 7, 8, 4]
- Output
- [8, 4, 10, 2, 7]
- Why
- Inorder traversal of tree produces [8, 2, 4, 10, 7]. Sorting gives [2, 4, 7, 8, 10]. Replacing values in inorder traversal converts original structure into valid BST.
Approach
Perform an inorder traversal to extract all node values into an array.
Sort the extracted array in non-decreasing order.
Perform an inorder traversal of the tree again, copying values from sorted array to tree nodes in order.
Ensure node child relationships (pointers) are untouched throughout the process.
Tips
- What they are testing: Evaluates tree traversal (inorder/preorder) and array sorting techniques to modify tree values in-place.
- Common mistake: Creating a new tree structure instead of preserving the given binary tree's existing structural shape.
Related Accolite questions
Collected from public candidate posts and coding forums. Updated Nov 2026.