#include <climits>
#include <queue>

typedef struct Holder {
  Node* node;
  int min;
  int max;
  Holder(Node* n, int min, int max): node(n), min(min), max(max) {}
} *Holder_p;

// Cracking the Coding Interview, Question 4.5
// Implement a function to check if a binary tree is a binary search tree
// See https://gist.github.com/lowellbander/d8c2bfcaebd8cbcdf755
// Tail Recursive (less elegant) implementation
bool isSearch(Node* root, int max = INT_MAX, int min = INT_MIN) {
  queue<Holder_p> q;
  q.push(new Holder(root, max, min));
  return isSearchHelper(*q);
}

bool isSearchHelper(*queue<Holder_p> q) {
  Holder_p hold = q->pop();
  if (!hold || !hold->node) return true;
  if (hold->node->value <= hold->min || hold->node->value > hold->max) return false;
  q.push(new Holder(hold->node->left, hold->min, hold->node->value));
  q.push(new Holder(hold->node->right, hold->node->value, hold->max));
  delete hold;
  return isSearchHelper(q);
}