Convert BST to Min Heap

The problem, simply

You get a binary search tree that is also complete (every row full except maybe the last, which fills from the left). Change the values, but not the shape, so that:

1. It is a min heap: every parent is smaller than its children.
2. For every node, all values in its left subtree are smaller than all values in its right subtree.

For the tree [4, 2, 6, 1, 3, 5, 7] the answer is [1, 2, 5, 3, 4, 6, 7].

A story to remember it

Picture it

Examples

Way 1: the simple way

Forget that the tree is a search tree. Collect every value in any order, sort them, and hand them out parent first, then left side, then right side (preorder).

1. Walk the tree and put every value in a list.
2. Sort the list.
3. Walk the tree in preorder and write the next value from the list into each node.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    private int next;

    public void convertToMinHeap(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        collect(root, vals);
        Collections.sort(vals);                 // O(n log n)
        next = 0;
        fill(root, vals);
    }

    private void collect(TreeNode node, List<Integer> vals) {
        if (node == null) return;
        vals.add(node.val);
        collect(node.left, vals);
        collect(node.right, vals);
    }

    private void fill(TreeNode node, List<Integer> vals) {   // preorder
        if (node == null) return;
        node.val = vals.get(next++);
        fill(node.left, vals);
        fill(node.right, vals);
    }
}

How long it takes: the sort costs O(n log n). Extra room: the list, O(n).

Way 2: the clever way

A search tree read in order (left, me, right) is already sorted. So skip the sort.

1. Walk the tree in order and put the values in a list. They come out sorted.
2. Walk the tree in preorder (me, left, right) and write the next value from the list into each node.

Why it works: preorder visits a parent before its children, so a parent always gets a smaller number. Preorder also finishes the whole left subtree before it starts the right subtree, so every left value is smaller than every right value. The shape never changes, so the tree stays complete.

import java.util.ArrayList;
import java.util.List;

class Solution {
    private int next;

    public void convertToMinHeap(TreeNode root) {
        List<Integer> sorted = new ArrayList<>();
        inorder(root, sorted);                  // sorted for free
        next = 0;
        preorderFill(root, sorted);
    }

    private void inorder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }

    private void preorderFill(TreeNode node, List<Integer> sorted) {
        if (node == null) return;
        node.val = sorted.get(next++);          // parent first: smallest left
        preorderFill(node.left, sorted);        // then the whole left side
        preorderFill(node.right, sorted);       // then the whole right side
    }
}

How long it takes: two walks over the tree, O(n). Extra room: the list of n values, O(n), plus O(log n) for the recursion because a complete tree is short.

Watch out for

• Use inorder to read, preorder to write. Swapping them breaks the answer.
• The counter next must be shared by all the recursive calls. A field or a one item array works. A plain int parameter does not.
• The shape must stay the same. Do not build a new tree unless the problem allows it.
• If the input tree is not complete, the result is not a heap in the usual sense. Ask before you start.

What interviewers ask next

• Convert a BST to a max heap with left smaller than right? Read inorder, then fill in postorder (left, right, me). The parent is filled last, so it gets the biggest value.
• Can you do it with less room? With Morris traversal you can read inorder without a stack, but you still need the n values somewhere, so the list stays.
• Convert a sorted array into a min heap? A sorted array is already a min heap in array form. No work needed.
• Convert a min heap into a BST? Sort the values (O(n log n), you cannot do better because a BST gives sorted order), then fill in inorder.

Remember this

Grown-up words: the family tree is a complete binary search tree, reading left, me, right is an inorder traversal, handing out parent first then left then right is a preorder traversal, and parent smaller than children is the min heap property.