Counting Treaps

Question

Consider the problem of counting the number of structurally distinct binary search trees:

Given N, find the number of structurally distinct binary search trees containing the values 1 .. N

It's pretty easy to give an algorithm that solves this: fix every possible number in the root, then recursively solve the problem for the left and right subtrees:

countBST(numKeys)
    if numKeys <= 1
        return 1
    else
        result = 0
        for i = 1 .. numKeys
            leftBST = countBST(i - 1)
            rightBST = countBST(numKeys - i)

            result += leftBST * rightBST

        return result

I've recently been familiarizing myself with treaps, and I posed the following problem to myself:

Given N, find the number of distinct treaps containing the values 1 .. N with priorities 1 .. N. Two treaps are distinct if they are structurally different relative to EITHER the key OR the priority (read on for clarification).

I've been trying to figure out a formula or an algorithm that can solve this for a while now, but I haven't been successful. This is what I noticed though:

1. The answers for n = 2 and n = 3 seem to be 2 and 6, based on me drawing trees on paper.
2. If we ignore the part that says treaps can also be different relative to the priority of the nodes, the problem seems to be identical to counting just binary search trees, since we'll be able to assign priorities to each BST such that it also respects the heap invariant. I haven't proven this though.

3. I think the hard part is accounting for the possibility to permute the priorities without changing the structure. For example, consider this treap, where the nodes are represented as (key, priority) pairs:

             (3, 5)
             /    \ 
        (2, 3)    (4, 4)
        /              \
   (1, 1)               (5, 2)
   

   We can permute the priorities of both the second and third levels while still maintaining the heap invariant, so we get more solutions even though no keys switch place. This probably gets even uglier for bigger trees. For example, this is a different treap from the one above:

             (3, 5)
             /    \ 
        (2, 4)    (4, 3) // swapped priorities
        /              \
   (1, 1)               (5, 2)
   

I'd appreciate if anyone can share any ideas on how to approach this. It seemed like an interesting counting problem when I thought about it. Maybe someone else thought about it too and even solved it!

Answer 1

def countBST(numKeys:Long):Long = numKeys match {
  case 0L => 1L
  case 1L => 1L
  case _ => (1L to numKeys).map{i=>countBST(i-1) * countBST(numKeys-i)}.sum
}

You didn't actually define structural similarity for treaps -- you just gave examples. I'm going to assume the following definition: two trees are structurally different if and only if they have a different shape, or there exist nodes a (from tree A) and b (from tree B) such that a and b are in the same position, and the priorities of the children of a are in the opposite order of the priorities of the children of b. (It's obvious that if two treaps on the same values have the same shape, then the values in corresponding nodes are the same.)

In other words, if we visualize two trees by just giving the priorities on the nodes, the following two trees are structurally similar:

      7               7
   6      5        6      5
  4 3    2 1      2 1    4 3  <--- does not change the relative order
                                   of the children of any node
                                   6's left child is still greater than 6's right child
                                   5's left child is still greater than 5's right child

but the following two trees are structurally different:

      7               7
   5      6        6      5   <--- changes the relative order of the children
  4 3    2 1      4 3    2 1       of node 7

Thus for the treap problem, each internal node has 2 orderings, and these two orderings do not otherwise affect the shape of the tree. So...

def countTreap(numKeys:Long):Long = numKeys match {
  case 0L => 1L
  case 1L => 1L
  case _ => 2 * countBST(numKeys-1) +  //2 situations when the tree has only 1 child
            2 * (2L to (numKeys-1)).map{i=>countBST(i-1) * countBST(numKeys-i)}.sum
            // and for each situation where the tree has 2 children, this node  
            // contributes 2 orderings the priorities of its children
            // (which is independent of the shape of the tree below this level)
}