TopCoder Statistics - Problem Statement

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 an 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:: int[]
Returns:: int
Method signature:: int howMany(int[] values)
(be sure your method is public)

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

{10}

Returns: 1

Only a single node
{90,12}

Returns: 2

Either 90 or 12 can be the parent node.
{1,2,3}

Returns: 5
{90,13,2,3}

Returns: 14
{-100000,12,42,0,10}

Returns: 42
{0,1,2,3,4,5,6}

Returns: 429
{1,2,3,4,5,6,7}

Returns: 429
{1,2,3,4,5,6,7,8}

Returns: 1430
{1,2,3,4,5,6,7,8,9}

Returns: 4862
{1,2,3,4,5,6,7,8,9,10}

Returns: 16796
{10000,9999,9998,9997,-10000,-9999,-9998,-9997,0,1}

Returns: 16796
{ 10000, 9999, 9998, 9997, -10000, -9999, -9998, -9997, 0, 1 }

Returns: 16796
{ 1, 2, 3, 4, 5, 6, 7, 8 }

Returns: 1430
{ 1, 2, 3, 4, 5, 6 }

Returns: 132
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Returns: 4862
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Returns: 16796
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }

Returns: 16796

Statistics

Problem Statement for "BSTs"

Problem Statement

Definition

Constraints

Examples