Clever Geek Handbook

Build a unique binary search tree

I am working on an algorithm problem. Given n, generate all structurally unique binary search trees that store the values ​​1 ... n. The solution was to list each number i in the sequence and use the number as the root, the subsequence 1 ... (i-1) on the left side will lie on the left branch of the root and similarly the right subsequence (i +1) ... n lies on the right branch of the root. Then build the subtree from the subsequence recursively. This approach ensures that the constructed BSTs are all unique as they have unique roots.

Now my question is, what if the trees are not limited to binary search trees, if it could be any binary tree. What would be the solution? I would still like to consider all cases with the root i, where i = 1, ... n. The left subtree must not be in the range 1 ... (i-1), the right subtree must not be in the range (i + 1) ... n. But then how to arrange them? Create an arbitrary subset of elements (i-1) and apply

+3


source to share


2 answers


Suppose you were given the following problem: if you specified n disks, arrange them in unique binary forms. Then, following your correct reasoning in the question, you can say the following: I will indicate drives 1, 2, 3, .., n; then I'll (recursively) build trees rooted on disk # 1, then on disk # 2, etc.

Thus, the trees you (correctly) found have nothing to do with the content in the nodes, let alone whether the content satisfies the BST invariant. Considering your question here,



  • If the question is how many root digraphs there are, then it will be the same as before.

  • If the question is how many combinations of root digraphs + node are there, then you simply list the root digraphs as you did, and for each you list the permutations 1, 2, ... n.

    If so, and you do not need to enumerate, but rather approximate the number of such trees, then note that it is n! multiplied by Catalan numbers .

+2


source


Use your own algorithm for BST. This generates unique tree shapes. 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 form there are n! ordering elements. This gives results for arbitrary trees.

+2


source






More articles:


All Articles