Algorithms: Design and Analysis, Part 1 - Problem Set 6 - Question 2

Problem:

You are given a binary tree (via a pointer to its root) with n nodes, which may or may not be a binary search tree. How much time is necessary and sufficient to check whether or not the tree satisfies the search tree property?

Solution:

A top down solution would look like this:

function check(Node node, int minimum, int maximum)
  if (node == null)
    return true;
  if (node.value > maximum)
    return false;
  if (node.value < minimum)

    return false;
  return check(node.left) && check(node.right)

The algorithm inspect every element exactly once, so it is $ O(n) $.

Suppose there exist an algorithm that can run asymptotically faster than $ O(n) $, it cannot inspect all nodes. If it cannot inspect all nodes, then the adversary is free to choose what value to put in that node. In particular, for a case when the algorithm return true, the adversary can always put a value in that not inspected node to invalid the validity of the tree as follow

Suppose the node being not inspected in the rightmost node, then the algorithm can put a value smaller than any value in the tree, that would sabotage the algorithm.

Otherwise, the algorithm can put a value that is larger than any value in the tree, the adversary can also sabotage the algorithm.

Therefore, in order to not get sabotaged, the algorithm must inspect all node, that prove the problem will take at least $ \Omega(n) $ time.