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 The depth of a node in a BST is defined as such: 1) The top node (root) has depth 0 2) Every node has depth 1 higher than its parent Usually, when given a list of distinct values, it is best to build a balanced binary search tree - a tree where the size of the left subtree is approximately the same as the size of the right subtree at each node. A balanced tree isn't always the best solution though. Given a int[] values of distinct values and a int[] probs containing the percentage chance of each element being accessed, your method will return the best (lowest) access score achievable by a BST containing the given values. The access score of any BST is computed by adding together the access scores for all of its nodes. The access score for a particular node is calculated by the formula p*(d+1) where p is the probability of that node being accessed, and d is the depth of that node in the tree. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Constraints | |||||||||||||
- | values and probs will both contain between 1 and 50 elements, inclusive. | ||||||||||||
- | Each element of values and probs will be between 1 and 1000, inclusive. | ||||||||||||
- | Each element of values will be unique. | ||||||||||||
- | values and probs will contain the same number of elements. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
|