Assume there is an implementation of binary tree ADI such th

Assume there is an implementation of binary tree ADI such that one can access its root, the key stored in each node, and the left and the right child of each node with O(1) complexity. Let T, given as input, be such an object with n nodes. Describe an algorithm that checks whether T is a valid binary search tree. Analyze the worst-case complexity of your algorithm. Assume T is a binary search tree and let k be another input. Describe an algorithm that finds one of the closest-to-k keys in the binary tree T. Analyze the worst-case complexity of your algorithm. (Assume all the keys are integers and the distance between two keys is the absolute value of their difference.)

Solution

bool isSubTreeLessThan(BinaryTree *p, int val) {

  if (!p) return true;

  return (p->data < val &&

          isSubTreeLessThan(p->left, val) &&

          isSubTreeLessThan(p->right, val));

}

bool isSubTreeGreaterThan(BinaryTree *p, int val) {

  if (!p) return true;

  return (p->data > val &&

          isSubTreeGreaterThan(p->left, val) &&

          isSubTreeGreaterThan(p->right, val));

}

bool isBSTBruteForce(BinaryTree *p) {

  if (!p) return true;

  return isSubTreeLessThan(p->left, p->data) &&

         isSubTreeGreaterThan(p->right, p->data) &&

         isBSTBruteForce(p->left) &&

         isBSTBruteForce(p->right);

}

bool isBSTHelper(BinaryTree *p, int low, int high) {

  if (!p) return true;

  if (low < p->data && p->data < high)

    return isBSTHelper(p->left, low, p->data) &&

           isBSTHelper(p->right, p->data, high);

  else

    return false;

}

bool isBST(BinaryTree *root) {

  // INT_MIN and INT_MAX are defined in C++\'s <climits> library

  return isBSTHelper(root, INT_MIN, INT_MAX);  

}

Alternat Solution :

bool isBSTInOrderHelper(BinaryTree *p, int& prev) {

  if (!p) return true;

  return (isBSTInOrderHelper(p->left, prev) &&

          (p->data > prev) && (prev = p->data) &&

          isBSTInOrderHelper(p->right, prev));

}

bool isBSTInOrder(BinaryTree *root) {

  int prev = INT_MIN;

  return isBSTInOrderHelper(root, prev);

}