When dealing with trees, algorithm complexity is usually measured in terms of the number of nodes in the tree while the elementary operation is usually a node traversal. Let T be a binary tree such that each node u has a parent , rightChild and leftChild and a key element, key . The left/right child may be null indicating it does not exist. Given a binary tree, we wish to determine if it is a binary search tree or not.

(a) Gomer thinks we can solve this problem by using a preorder traversal. When each node u is processed, it simply verifies that the left childs key is strictly less than us key and us right childs key is strictly greater than us key. Gomers solution, however, will not work. Provide a counter example to demonstrate this and explain how it shows Gomer is wrong.

(b) Design a correct algorithm that, given a root note in a binary tree (with parent , rightChild , leftChild and key elements) determines if it is a binary search tree or not. Fully analyze your algorithm.