(a) A student believes that Binary Search Trees possess the following property. Suppose we search for a key and the matching node is a leaf node. Let L be the set of all nodes to the left of the search path, P the set of all nodes on the search path, and R be the set of all nodes to the right of the search path. The student claims that any three keys l ? L, p ? P, and r ? R must satisfy l ? p ? r. Give a simple counter-example to prove that it is not the case. (2 marks)

(b) Is the DeleteItem() operation for Binary Search Trees commutative? That is, does deleting nodes X then Y result in the same tree as deleting nodes Y then X? Argue why it is true or else give a counter-example. (2 marks)