construct unique binary search tree

4
votes

I'm working on an algorithm problem. Given n, generate all structurally unique binary search trees that store values 1...n. The solution was to enumerate each number i in the sequence, and use the number as the root, the subsequence 1…(i-1) on its left side would lay on the left branch of the root, and similarly the right subsequence (i+1)…n lay on the right branch of the root. Then construct the subtree from the subsequence recursively. This approach ensures that the BST constructed are all unique, since they have unique roots.

Now my question is: what if the trees are not limited to binary search trees, if it can be any binary tree. How would the solution be? I'd still want to go over all the cases with root i, where i = 1, ... n. The left subtree doesn't have to be in the range of 1...(i-1), right subtree doesn't have to be in the range of (i+1)...n. But then how to arrange them then? Create an arbitrary subset of (i-1) elements and apply??

2
algorithmtreedynamic-programming
Making it a binary search tree (or not) doesn't affect the structures possible in the three, only the order of the data in the nodes of that structure. As such, unless you're defining "structurally unique" in some rather strange way, it makes no difference whether the nodes are ordered as a BST or not. - Jerry Coffin

2 Answers

3
votes

Suppose you were given the following problem: given n disks, arrange them in unique binary-tree shapes. Then, following your correct reasoning in the question, you could say the following: I'll number the disks 1, 2, 3, .., n; then I'll (recursively) build the trees whose root is at disk #1, then disk #2, etc.

So the tree rooted-digraphs you (correctly) found really have nothing to do with the content in the nodes, let alone the question of whether the contents satisfied the BST invariant. Given your question here,

  1. If the question is how many rooted digraphs exist, then it's the same as before.

  2. If the question is how many combinations of rooted digraphs + node contents there are, then you just enumerate the rooted digraphs as you've done, and, for each one, enumerate the permutations of 1, 2, ... n.

    If this is the case, and you don't need to enumerate, but rather approximate the number of such trees, then note that this is n! multiplied by the Catalan Numbers.

2
votes

Use your algorithm for BSTs. This generates the unique shapes of trees. The shapes are unique, because for each root n there are n-1 elements in the left subtree, the rest are on the right.

Then, for each shape, there are n! orderings of elements. This gives the results for arbitrary trees.