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:

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 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 } };

Notes
(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
Last modified: Tue Jan 6 09:47:33 EST 2004

Weekly Problem #9

Problem Statement

Definition

Class

Notes

Constraints

Examples