Create evenly 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 satisfy the property that

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

Curious binary tree example

4 / \ 5 2 / \ 1 3 

Can you give an algorithm for generating a uniformly random curious binary tree of n nodes that works in O (n) guaranteed time?

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

O (nlogn) time solution will also get my upvote.

Please follow the usual definitions of labeled binary trees that are excellent to view various curious binary trees.

Answer 1

Yeah, I think I have how to create a random heap in O (N) time. (Then use the approach in Greg Kuperberg to convert to a "curious" binary tree.)

edit 2 : a crude pseudo code to create a random mini-heap directly. The max heap is identical except for the values ​​inserted in the heap in the reverse 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); } 

Answer 2

There is a bijection between the "curious" binary trees and standard heaps. Namely, given the heap, recursively (starting at the top) swap each inner node with its largest child. And, as I recently learned in StackOverflow, a heap is equivalent to a permutation of 1,2, ..., N. Therefore, you must do an arbitrary permutation and turn it into a heap; or recursively do a bunch just as if you did an arbitrary permutation. After that, you can convert the pile into a "curious tree."