<p>While Per Vognsen's comment works well for labeled trees, your question uses the word "unique" (which should probably be "distinct") to describe the shape of the tree.  This makes me think you mean "How many isomorphism classes of unlabeled binary trees are there?"</p>

<p>To compute this exactly, you will probably want to use <a href="http://cs.anu.edu.au/~bdm/">Brendan McKay</a>'s <a href="http://cs.anu.edu.au/~bdm/papers/orderly.pdf">"Isomorph-free exhaustive generation"</a> which he uses in his program <code>geng</code> to list each isomorphism class of simple graphs on a given number of vertices and edges, and do it quickly.</p>

<p>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 <code>nauty</code> library.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-12T03:42:25.707Z
2010-11-12T03:42:25.707Z
Derrick Stolee
<p>Say you have a set of numbers {1,2,3,4,5,6,7,8,9,10} of which you have all different permutations.</p>

<p>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?</p>

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

CC BY-SA 2.5
2010-09-23T22:15:58.977Z
what is the "shape" of a tree ? For any permutation, I can always change the shape by rotations, while preserving the ordering.
Suresh Venkat
CC BY-SA 2.5
2010-09-23T22:33:14.920Z
[Catalan numbers](http://mathworld.wolfram.com/CatalanNumber.html) give the *total* number of different "shapes" of binary trees.
Jukka Suomela
CC BY-SA 2.5
2010-09-23T23:31:03.130Z
@Jukka: so if that gives the total, trying to get the ones of a particular height would require what kind of computation?
Sev
CC BY-SA 2.5
2010-09-24T00:42:51.833Z
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
CC BY-SA 2.5
2010-09-24T05:56:52.030Z
@Per, good comment: would be an even better answer :)
Suresh Venkat
<ds.algorithms>
Unique Shapes of Binary Search Trees
Sev
# Unique Shapes of Binary Search Trees

(Asked by: username_0 on 2010-09-23)

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.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: what is the "shape" of a tree ? For any permutation, I can always change the shape by rotations, while preserving the ordering.  
> **username_2**: [Catalan numbers](http://mathworld.wolfram.com/CatalanNumber.html) give the *total* number of different "shapes" of binary trees.  
> **username_0**: @Jukka: so if that gives the total, trying to get the ones of a particular height would require what kind of computation?  
> **username_3**: 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.  
> **username_1**: @Per, good comment: would be an even better answer :)  

---

## 1 answers

### Answer by username_4 on 2010-11-12. Score: 8 | Accepted answer

While username_3's comment works well for labeled trees, your question uses the word "unique" (which should probably be "distinct") to describe the shape of the tree. This makes me think you mean "How many isomorphism classes of unlabeled binary trees are there?"

To compute this exactly, you will probably want to use [Brendan McKay](http://cs.anu.edu.au/~bdm/)'s ["Isomorph-free exhaustive generation"](http://cs.anu.edu.au/~bdm/papers/orderly.pdf) 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.


---

