# Weekly Problem #9

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.

### 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:
1. Every node has a unique VALUE

2. The VALUE at a given node must be greater than the VALUE at every node in its left subtree

3. 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 BSTs that contains the method howMany, which takes a `tvector<int> values`, and returns an int that represents the number of distinct possible BSTs resulting from the given set of values.

### Definition

• Class: BSTs
• Method: howMany
• Parameters: `const tvector<int>&`
• Returns: `int`
• Method signature:
```    int howMany(const tvector<int>& values)
```
(be sure your method is public)

### Class

#include "tvector.h" class BSTs { public: int howMany(const tvector<int>& values) { // fill in code here } };

(none)

### Constraints

• `values` will contain between 1 and 10 elements inclusive

• Each element of `values` will be between -1000000 and 1000000 inclusive

• `values` will not contain repeated elements.

### Examples

1. ```values = {10}

```
Returns: 1

Only a single node

2. ```

values = {90,12}

```
Returns: 2

Either 90 or 12 can be the parent node.

3. ```

values = {90,13,2,3}
```

Returns: 14

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

```

Returns: 16796

Owen L. Astrachan