Convert a BST to a min-heap

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}