Skip to content

Instantly share code, notes, and snippets.

@Goom11
Forked from n2westman/isSearch.cpp
Last active August 29, 2015 14:12
Show Gist options
  • Save Goom11/1fe2d4f39045ba726c09 to your computer and use it in GitHub Desktop.
Save Goom11/1fe2d4f39045ba726c09 to your computer and use it in GitHub Desktop.
#include <climits>
#include <stack>
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
// Also see https://gist.github.com/n2westman/371494b4da13b30b4ffa
// Tail Recursive (less elegant) implementation
// Using stack instead of queue for smaller space complexity while maintaining the same time complexity
bool isSearch(Node* root, int max = INT_MAX, int min = INT_MIN) {
stack<Holder_p> s;
s.push(new Holder(root, max, min));
return isSearchHelper(*s);
}
bool isSearchHelper(*stack<Holder_p> s) {
if(s->empty()) return true;
Holder_p hold = s->pop();
if (!hold->node) return isSearchHelper(s);
if (hold->node->value <= hold->min || hold->node->value > hold->max) return false;
s->push(new Holder(hold->node->left, hold->min, hold->node->value));
s->push(new Holder(hold->node->right, hold->node->value, hold->max));
delete hold;
return isSearchHelper(s);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment