3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ what is the "shape" of a tree ? For any permutation, I can always change the shape by rotations, while preserving the ordering. $\endgroup$ – Suresh Venkat Sep 23 '10 at 22:15
  • 3
    $\begingroup$ Catalan numbers give the total number of different "shapes" of binary trees. $\endgroup$ – Jukka Suomela Sep 23 '10 at 22:33
  • $\begingroup$ @Jukka: so if that gives the total, trying to get the ones of a particular height would require what kind of computation? $\endgroup$ – Sev Sep 23 '10 at 23:31
  • 6
    $\begingroup$ 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. $\endgroup$ – Per Vognsen Sep 24 '10 at 0:42
  • 2
    $\begingroup$ @Per, good comment: would be an even better answer :) $\endgroup$ – Suresh Venkat Sep 24 '10 at 5:56
8
$\begingroup$

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?"

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.