Your friend believes they have come up with a new kind of binary search tree he claims is more efficient than a red-black tree. It is a data structure that stores data in a binary search tree. Your friend claims that it has the following operations: treeInsert(k) inserts an item with key k into the tree, maintaining the BST property. It does not return anything. It runs in time O(1). treeSearch(k) finds and returns a pointer to node with key k, if it exists in the tree. It runs in time O(log(n)), where n is the number of items in the tree. treeDelete(k) removes and returns a pointer to an item with key k, if it exists in the tree, maintaining the BST property. It runs in time O(log(n)), where n is the number of items in the tree Your friend says that all of these operations are deterministic, and that their tree can handle arbitrary comparable objects.

You think that this logic is flawed, how do you know that it is wrong?

[We are expecting a formal proof that your friend is wrong.]