APT: Counting BSTs

Class

public class BSTcount { public long howMany(int[] values) { // fill in code here } }

Problem Statement

In a binary tree every node has an optional left, and optional right child node. A BST(binary search tree) is a binary tree that satsifies the following properties:

Every node has a unique VALUE
The VALUE at a given node must be greater than the VALUE at every node in its left subtree
The VALUE at a given node must be less than the VALUE at every node in its right subtree

A set of VALUEs can have multiple BSTs associated with it depending on how the nodes are arranged. For example: values = {3,2,1}


  1      |  1    |    2    |      3  |    3
   \     |   \   |   / \   |     /   |   /
    2    |    3  |  1   3  |    2    |  1
     \   |   /   |         |   /     |   \
      3  |  2    |         |  1      |    2

The set {3,2,1} has 5 possible BSTs shown above. Two BSTs are different if they differ in the position of at least one VALUE.

Given a set of VALUEs you will determine how many BSTs are possible.

Create a class BSTcount that contains the method howMany, which takes a int[] values, and returns a long value that represents the number of distinct possible BSTs resulting from the given set of values.

Constraints

values will contain between 1 and 25 elements inclusive
Each element of values will be between -1000000 and 1000000 inclusive
values will not contain repeated elements.

Examples

```
values = {10}

Returns: 1
```
Only a single node
```
values = {90,13,2,3}

Returns: 14
```
```
values = {90,12}

Returns: 2
```
Either 90 or 12 can be the parent node.


values = {10000,9999,9998,9997,-10000,-9999,-9998,-9997,0,1}

Returns: 16796

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2002, TopCoder, Inc. All rights reserved.