Generating uniformly random curious binary trees.

Question

A binary tree of N nodes is 'curious' if it is a binary tree whose node values are 1, 2, ..,N and which satisfy the property that

• Each internal node of the tree has exactly one descendant which is greater than it.
• Every number in 1,2, ..., N appears in the tree exactly once.

Example of a curious binary tree

  4
 / \
5   2
   / \
   1  3

Can you give an algorithm to generate a uniformly random curious binary tree of n nodes, which runs in O(n) guaranteed time?

Assume you only have access to a random number generator which can give you a (uniformly distributed) random number in the range [1, k] for any 1 <= k <= n. Assume the generator runs in O(1).

An O(nlogn) time solution will get my upvote too.

Please follow the usual definition of labelled binary trees being distinct, to consider distinct curious binary trees.

Answer 1

There is a bijection between "curious" binary trees and standard heaps. Namely, given a heap, recursively (starting from the top) swap each internal node with its largest child. And, as I learned in StackOverflow not long ago, a heap is equivalent to a permutation of 1,2,...,N. So you should make a random permutation and turn it into a heap; or recursively make the heap in the same way that you would have made a random permutation. After that you can convert the heap to a "curious tree".

Answer 2

Aha, I think I've got how to create a random heap in O(N) time. (after which, use approach in Greg Kuperberg's answer to transform into "curious" binary tree.)

edit 2: Rough pseudocode for making a random min-heap directly. Max-heap is identical except the values inserted into the heap are in reverse numerical order.

struct Node {
   Node left, right;
   Object key;
   constructor newNode() { 
     N = new Node; 
     N.left = N.right = null; 
     N.key = null;
   }
}

function create-random-heap(RandomNumberGenerator rng, int N)
{
   Node heap = Node.newNode();
   // Creates a heap with an "incomplete" node containing a null, and having
   // both child nodes as null.

   List incompleteHeapNodes = [heap];
   // use a vector/array type list to keep track of incomplete heap nodes.

   for k = 1:N
   {
      // loop invariant: incompleteHeapNodes has k members. Order is unimportant.

     int m = rng.getRandomNumber(k);
     // create a random number between 0 and k-1
     Node node = incompleteHeapNodes.get(m);
     // pick a random node from the incomplete list, 
     // make it a complete node with key k.
     // It is ok to do so since all of its parent nodes
     // have values less than k.
     node.left = Node.newNode();
     node.right = Node.newNode();
     node.key = k;

     // Now remove this node from incompleteHeapNodes
     // and add its children. (replace node with node.left,
     // append node.right)

     incompleteHeapNodes.set(m, node.left);
     incompleteHeapNodes.append(node.right);

     // All operations in this loop take O(1) time.
   }

   return prune-null-nodes(heap);
}

// get rid of all the incomplete nodes.
function prune-null-nodes(heap)
{
   if (heap == null || heap.key == null)
      return null;
   heap.left = prune-null-nodes(heap.left);
   heap.right = prune-null-nodes(heap.right);
}