Write BstRange. Read n and n keys into a BST, then low high k. Print:
- the keys in [low, high] in increasing order, using an in-order traversal that prunes subtrees that cannot contain such keys (go left only if
low < key, right only ifkey < high), and the number of nodes visited (non-null nodes on which the method is called); - the k-th smallest key (
noneif k > n), by an in-order walk that stops early; - the height (a single node has height 0) and the result of
isBst, which checks that every key lies strictly between the bounds inherited from its ancestors; - if the root has a left child: set that child's key to
root.key + 1and runisBstagain.
For the input
9
50 30 70 20 40 60 80 35 45
33 62 3
the program prints
Keys in [33, 62]: [35, 40, 45, 50, 60]
Nodes visited: 7 of 9
Smallest #3: 35
Height: 3, valid BST: true
After corrupting the left child: valid BST: false