What would be the time complexity of counting the number of all structurally different binary trees?

Question

Using the method presented here: http://cslibrary.stanford.edu/110/BinaryTrees.html#java

  12. countTrees () Solution (Java)
 / **
  For the key values ​​1 ... numKeys, how many structurally unique
  binary search trees are possible that store those keys?

  Strategy: consider that each value could be the root.
  Recursively find the size of the left and right subtrees.
 * /
 public static int countTrees (int numKeys) {
   if (numKeys <= 1) {
     return (1);
   }
   else {
     // there will be one value at the root, with whatever remains
     // on the left and right each forming their own subtrees.
     // Iterate through all the values ​​that could be the root ...
     int sum = 0;
     int left, right, root;

     for (root = 1; root <= numKeys; root ++) {
       left = countTrees (root-1);
       right = countTrees (numKeys - root);

       // number of possible trees with this root == left * right
       sum + = left * right;
     }

     return (sum);
   }
 } 

I mean that it can be n (n-1) (n-2) ... 1, i.e. n!

If using memoizer, is that O (n) complexity?

Answer 1

The number of complete binary trees with the number of nodes n is the nth Catalan number. Catalan numbers are calculated as

which is the complexity of O (n).

http://mathworld.wolfram.com/BinaryTree.html

http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics

Answer 2

It is easy enough to count the number of calls countTrees that this algorithm uses for a given counter node. After several trial runs, it seems to me that this requires 5 * 3 ^ (n-2) calls for n> = 2, which grows much more slowly than n !. The proof of this statement remains as an exercise for the reader. :-)

The memorable version requires O (n) calls, as you expected.

By the way, the number of binary trees with n nodes is the n-th Catalan number . Obvious approaches to computing C _n seem linear in n, so it is probably best to implement a memoized implementation of countTrees .

Answer 3

I'm not sure how many hits on the lookup table are a memorialized version that will do (which is definitely super linear and will have the overhead of calling the function), but with mathematical proof bringing the same result as the nth Catalan number, you can quickly prepare the tabular method with linear time:

  int C=1; for (int i=1; i<=n; i++) { C = (2*(2*(i-1)+1)*C/((i-1)+2)); } return C; 

Note the difference between Memoization and Tabulation here