BSTs

SRM 132 · 2003-02-01 · by brett1479

Class Name: BSTs

Return Type: int

Method Name: howMany

Arg Types: (vector<int>)

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.

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

Submissions are judged against all 17 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BSTs with a public method int howMany(vector<int> values) · 17 test cases · 2 s / 256 MB per case