*This statement contains images which must be viewed in the applet.*
A *Binary Search Tree (BST)* is a tree data structure which obeys the following properties:
- Each node has at most 2 children.
- Each node except the root has exactly 1 parent.
- There is exactly 1 root node. The root node does not have any parents.
- If a node has a left child, all values in the left subtree are less than or equal to the value of the node itself.
- If a node has a right child, all values in the right subtree are strictly greater than the value of the node itself.
In this problem, nodes are identified starting from the root node as 1, and following in order with nodes at the next level, etc. See the figure below for clarification.
You will be given a BST with one node value that is missing. You must determine the possible values that the node can represent so as to maintain a valid BST according to the above rules.
Create a class IncompleteBST that contains a method missingValues. The method takes a String[] **tree** as input and returns a String corresponding to the possible values (from among 'A' to 'Z') that the missing character can assume so as to maintain a valid BST. Each element of **tree** is formatted as follows: "CHARACTER INTEGER" (quotes for clarity only). That is, a single character followed by a single space followed by a single integer. The CHARACTER denotes the value of the particular node in the BST. In exactly one element of **tree**, CHARACTER will be '?', denoting the unknown missing value. The INTEGER denotes a particular node in the BST according to the above numbering scheme.
Note that **tree** will always contain a root node numbered 1. Furthermore, **tree** will represent a connected tree, that is, all nodes present in the tree will be reachable from the root node. The returned String must be sorted in ascending order and must contain distinct values only. If **tree** does not represent a valid BST, return an empty string; see the examples for clarification. |