Convert Binary tree into BST

The problem, simply

You get a binary tree with numbers in no special order. Change it into a binary search tree (BST): at every spot, smaller numbers on the left side, bigger on the right side.

The catch: the shape must stay exactly the same. You may not move any branch. You may only change which number sits in which spot.

A story to remember it

Picture it

Examples

Way 1: the simple way

Take the eggs out, but do not sort them. Visit the cups left to right, and for each cup search the whole pile for the smallest egg left, take it out and put it in.

1. Collect every number into a list.
2. Visit the spots in left, me, right order.
3. At each spot, scan the list for the smallest number, remove it, and write it into the spot.

import java.util.*;

class Solution {
    public TreeNode binaryTreeToBST(TreeNode root) {
        List<Integer> pile = new ArrayList<>();
        collect(root, pile);
        fill(root, pile);
        return root;
    }

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

    private void fill(TreeNode node, List<Integer> pile) {
        if (node == null) return;
        fill(node.left, pile);
        int best = 0;
        for (int i = 1; i < pile.size(); i++) {        // find the smallest egg left
            if (pile.get(i) < pile.get(best)) best = i;
        }
        node.val = pile.remove(best);
        fill(node.right, pile);
    }
}

How long it takes: each of the n spots scans up to n numbers, O(n^2). Extra room: the pile, O(n).

Way 2: the clever way

Sort the eggs once, then pour them back.

1. Collect every number into an array.
2. Sort the array.
3. Visit the spots in left, me, right order with a finger k on the sorted array. Each spot gets sorted[k], then k moves forward.

Why it works: in a BST, reading left, me, right always gives sorted order. We fill the spots in that reading order with sorted numbers, so the reading comes out sorted, so it is a BST.

import java.util.*;

class Solution {
    private int k;

    public TreeNode binaryTreeToBST(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        collect(root, vals);
        Collections.sort(vals);                 // line the eggs up
        k = 0;
        fill(root, vals);                       // put them back left to right
        return root;
    }

    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) {
        if (node == null) return;
        fill(node.left, vals);
        node.val = vals.get(k++);               // the next smallest egg
        fill(node.right, vals);
    }
}

How long it takes: sorting is O(n log n), the two walks are O(n), so O(n log n). Extra room: the list, O(n), plus O(h) for the recursion.

Watch out for

• Filling in "me, left, right" order. Only left, me, right gives a BST.
• Using a TreeSet to sort. It drops repeated numbers, and then you run out of eggs. Use a list and sort it.
• Keeping k as a parameter instead of a field. Each call would get its own copy and the numbers repeat.

What interviewers ask next

• Fewest swaps to turn the tree into a BST, keeping the shape. Write the numbers in reading order, then it becomes "fewest swaps to sort an array": count the cycles of the sorting permutation. O(n log n).
• Can you avoid the extra list? Turn the tree into a sorted linked list in place, then refill. In an interview, O(n) extra room is usually fine.
• What if the tree is a complete tree stored in an array? Same idea: the reading order of array positions is fixed, so fill those positions with the sorted numbers.
• Is the result balanced? Only if the original shape was. The shape is not allowed to change.

Remember this

Grown-up words: the cups are nodes, reading left, me, right is an inorder traversal, lining up the eggs is sorting, and keeping the carton is preserving the tree structure.