# Unique Shapes of Binary Search Trees

Say you have a set of numbers {1,2,3,4,5,6,7,8,9,10} of which you have all different permutations.

You place each permutation into a BST and then compare all the shapes of the BSTs. How many different (unique) shapes are there for trees of height 6 for example?

The question does not need to be answered directly, instead maybe an algorithm to help determine the shape instead and compare.

• what is the "shape" of a tree ? For any permutation, I can always change the shape by rotations, while preserving the ordering. – Suresh Venkat Sep 23 '10 at 22:15
• Catalan numbers give the total number of different "shapes" of binary trees. – Jukka Suomela Sep 23 '10 at 22:33
• @Jukka: so if that gives the total, trying to get the ones of a particular height would require what kind of computation? – Sev Sep 23 '10 at 23:31
• This seems a bit too elementary. Let f(n,h) be the number of binary trees with n nodes of height h and let g(n,h) be the number of binary trees with n nodes of height at most h. Then you get a pair of coupled recurrences, f(n,h) = 2 sum(k=1..n-1) f(k, h-1) g(n-k-1, h-1) and g(n,h) = sum(k=0..h) f(n,k), which you can evaluate efficiently with dynamic programming. Maybe that isn't completely right for what you want, but it should give you the right idea. – Per Vognsen Sep 24 '10 at 0:42
• @Per, good comment: would be an even better answer :) – Suresh Venkat Sep 24 '10 at 5:56

To compute this exactly, you will probably want to use Brendan McKay's "Isomorph-free exhaustive generation" which he uses in his program geng to list each isomorphism class of simple graphs on a given number of vertices and edges, and do it quickly.
To summarize his process, he uses a depth-first search on graphs, where each deepening step adds a vertex. To make sure no isomorphism class is repeated (which would happen a lot if this was done naïvely) the vertex-added graph decides if this was the "canonical" subgraph to use in the search. The algorithm essentially picks a vertex in the graph to be deleted using a canonical labeling of the graph and tests if this was the vertex that was added. A canonical labeling can be found by McKay's nauty library.
In your binary tree example, you would add a leaf somewhere in the tree. You can fix the root, but the other vertices may permute based on the automorphism group. Hence, you only need to test adding a leaf to each orbit of vertices that has fewer than two children. After adding the leaf, compute the canonical labeling of the tree and find the lexicographically-least leaf. If this leaf is in the same orbit as the leaf you added, then the search can deepen; otherwise try a new leaf. When $n$ vertices are reached, increment your counter.