Convert a BST to a min-heap
Problem
Given a BST that is a complete binary tree, rearrange its values in place so it becomes a min-heap in which every left subtree's values are smaller than every right subtree's values (preorder = sorted order).
Example 1
Input: BST [4, 2, 6, 1, 3, 5, 7] Output: [1, 2, 5, 3, 4, 6, 7]
Also asked as: Convert BST to Min Heap
Test cases
Case 1
Input: [4,2,6,1,3,5,7] Expected: [1,2,5,3,4,6,7]
Case 2
Input: [2,1,3] Expected: [1,2,3]
Case 3
Input: [1] Expected: [1]
View solutionHide solution1 approach
1. In-order values → fill nodes in pre-order
Time O(n)Space O(n)
In-order of a BST is sorted. Traverse the tree in pre-order and assign the sorted values in sequence — every parent then gets a smaller value than its children (a min-heap where the left subtree is entirely smaller than the right).
function bstToMinHeap(root) { const vals = []; (function inorder(n) { if (n) { inorder(n.left); vals.push(n.val); inorder(n.right); } })(root); let i = 0; (function preorder(n) { if (n) { n.val = vals[i++]; preorder(n.left); preorder(n.right); } })(root); return root;}