Question 1
(1) (2) (3) (4) A 10 cat 15 / \ / / \ / \ B C 5 bat rat 5 22 / / \ \ -3 ant 20 30
Tree 1 is not a BST because B is greater than A, yet B is in the left subtree of the node with key A (all keys in a node's left subtree should have keys that are less than the key in that node).
Tree 4 is not a BST because 20 is greater than 15, yet 20 is in the left subtree of the node with key 15.
Question 2
The BST that results from inserting the values 5 3 7 6 2 1 4 in that order is:
5 / \ 3 7 / \ / 2 4 6 / 1
The BST that results from inserting the values 1 2 3 4 5 6 7 in that order is:
1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7
The BST that results from inserting the values 4 3 5 2 6 1 7 in that order is:
4 / \ 3 5 / \ 2 6 / \ 1 7
private K smallest(BinaryTreenode<K> n) // precondition: n is not null // postcondition: return the smallest value in the subtree rooted at n { if (n.getLeft() == null) { return n.getKey(); } else { return smallest(n.getLeft()); } }