BST.cpp

#include <limits>

struct Nil {
  typedef int type;
};

template <int V, class L = Nil, class R = Nil> struct BTree {
  typedef decltype(V) type;
  static const type value = V;
  typedef L left;
  typedef R right;
};

template <class T,
	  typename T::type min = std::numeric_limits<typename T::type>::min(),
	  typename T::type max = std::numeric_limits<typename T::type>::max()>
struct isBSTree {
  static const bool value = T::value >= min &&
                            T::value < max &&
	                    isBSTree<typename T::left, min, T::value>::value &&
	                    isBSTree<typename T::right, T::value + 1, max>::value;
};

template <int min, int max> struct isBSTree<Nil, min, max> : public std::true_type {};

int
main()
{
  static_assert(isBSTree<BTree<5, BTree<2, BTree<1, BTree<0, BTree<-1>>>>>>::value, "This is a binary tree");
  static_assert(isBSTree<BTree<5, BTree<2, BTree<1, BTree<0, BTree<1>>>>>>::value, "This is not a binary tree");

  return 0;
}