Sort BST in O(n) using constant memory

Question

This is not a homework. Just an interesting task :)

Given a complete binary search three represensted by array. Sort the array in O(n) using constant memory.

Example:

Tree:

              8
           /     \
          4       12
         /\       / \
        2  6     10  14
       /\  /\    /\   /\
      1 3 5  7  9 11 13 15

Array: 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15

Output: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Answer 1

Thinking about the O(1) in-place variant, but for now here's the O(N) solution

An O(N) space solution

If you can use an O(N) output array, then you can simply perform an inorder traversal. Every time you visit a node, add it to the output array.

Here's an implementation in Java:

import java.util.*;
public class Main {
    static void inorder(int[] bst, List<Integer> sorted, int node) {
        if (node < bst.length) {
            inorder(bst, sorted, node * 2 + 1);
            sorted.add(bst[node]);
            inorder(bst, sorted, node * 2 + 2);
        }
    }
    public static void main(String[] args) {
        int[] bst = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
        final int N = bst.length;
        List<Integer> sorted = new ArrayList<Integer>();
        inorder(bst, sorted, 0);
        System.out.println(sorted);
        // prints "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]"
    }
}

Attachment

• Source and output on ideone.com

Answer 2

It is possible, people calling it homework probably haven't tried solving it yet.

We use the following as a sub-routine:

Given an array a1 a2 ... an b1 b2 .. bn, convert in O(n) time and O(1) space to

b1 a1 b2 a2 ... bn an

A solution for that can be found here: http://arxiv.org/abs/0805.1598

We use that as follows.

Do the above interleaving for the first 2^(k+1) - 2 elements, starting at k=1 repeating for k=2, 3 etc, till you go past the end of array.

For example in your array we get (interleaving sets identified by brackets)

 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15   
[ ][ ]

 4, 8, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15   (k = 1, interleave 2)
[        ][        ]  

 2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15   (k = 2, interleave 6)
[                      ][                     ]

 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15   (k = 3, interleave 14)

So the total time is n + n/2 + n/4 + ... = O(n). Space used is O(1).

That this works can be proved by induction.