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.
const tvector<int>&
int
int howMany(const tvector<int>& values)(be sure your method is public)
values
will contain between 1 and 10 elements inclusive
values
will be between -1000000 and 1000000 inclusive
values
will not contain repeated elements.
values = {10}Returns: 1
Only a single node
values = {90,12}Returns: 2
Either 90 or 12 can be the parent node.
values = {90,13,2,3}
Returns: 14
values = {10000,9999,9998,9997,-10000,-9999,-9998,-9997,0,1}
Returns: 16796