Skip to content

Instantly share code, notes, and snippets.

@n2westman

n2westman/isSearch.cpp

Last active August 29, 2015 14:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save n2westman/371494b4da13b30b4ffa to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save n2westman/371494b4da13b30b4ffa to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. n2westman revised this gist Jan 1, 2015. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion isSearch.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -19,8 +19,9 @@ bool isSearch(Node* root, int max = INT_MAX, int min = INT_MIN) {
    }

    bool isSearchHelper(*queue<Holder_p> q) {
    if(q->empty()) return true;
    Holder_p hold = q->pop();
    if (!hold || !hold->node) return true;
    if (!hold->node) return isSearchHelper(q);
    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));
  2. n2westman renamed this gist Jan 1, 2015. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions isSearch → isSearch.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -22,8 +22,8 @@ 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));
    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);
    }
  3. n2westman renamed this gist Jan 1, 2015. 1 changed file with 0 additions and 0 deletions.
    0 gistfile1.cpp → isSearch
    View file
    File renamed without changes.
  4. n2westman revised this gist Jan 1, 2015. No changes.
  5. n2westman created this gist Jan 1, 2015.
    29 changes: 29 additions & 0 deletions gistfile1.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,29 @@
    #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);
    }