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