Algorithm to check if a tree is a binary search tree

gistfile1.txt

> emacs thing.cpp

#include <iostream>
#include <algorithm>
using namespace std;

template <class T>
class Node {
public:
  Node* right;
  Node* left;
  T value;
};

// This algorithm runs in O(n) doesn't require                                                                                               
// n space through the use of an extra vector of nodes                                                                                       
//                                                                                                                                           
//  While traversing left change the max value to be                                                                                         
//  that of the previously visted nodes on the left subtree.                                                                                 
//  When traversing the right subtree make sure nodes are greater                                                                            
template <class T>
bool isBST(Node<T>* node, T min_value, T max_value) {
  if (!node)
    return true;

  // Make sure that node is between min and max                                                                                              
  // Recursively call left and right subtrees                                                                                                
  if (min_value < node->value && max_value > node->value) {
    if (isBST(node->left, min_value, node->value) &&
        isBST(node->right, node->value, max_value))
      return true;
  }
  return false;
}


int main() {
  Node<int>* a = new Node<int>();
  Node<int>* b  = new Node<int>();
  Node<int>* c  = new Node<int>();
  a->value = 10;
  b->value = 11;
  c->value = 30;

  b->left = a;
  b->right = c;

  cout << isBST(b, 0, 99999999) << endl;
  return 0;
}