Generating uniformly random curious binary trees

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

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).

I would like to see an O(nlogn) time solution too.

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

Solution

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);
}