Implement a function to check if a binary tree is a binary searchtree.

CareerCup4.5.cpp

#include <iostream>

struct Node
{
  	int data;
	Node* leftchild;
	Node* rightchild;
	Node()
	{
		leftchild=NULL;
		rightchild=NULL;
	}
};
Node* MakeSearchTree(int*, int*);
bool IsbinarySearchTree(Node*,int&,int&);

int main()
{
	int a[10] = {1,2,3,4,5,6,7,8,9,10};
	Node *root = MakeSearchTree(&a[0],&a[9]);
	int min,max;
	std::cout<<(IsbinarySearchTree(root,min,max)?"Is ":"Is not ")<<"binary search tree"<<std::endl;
	return 0;
}

bool IsbinarySearchTree(Node* node,int& min, int& max)
{
	min = node->data;
	max = node->data;
	if(node->leftchild!=NULL)
	{
		int leftmax,leftmin;
		if(!IsbinarySearchTree(node->leftchild,leftmin,leftmax))
		{
			return false;
		}
		else
		{
			if(leftmax>node->data)
			{
				return false;
			}
			else
			{
				min=leftmin;
			}
		}
	}
	if(node->rightchild!=NULL)
	{
		int rightmax,rightmin;
		if(!IsbinarySearchTree(node->rightchild,rightmin,rightmax))
		{
			return false;
		}
		else
		{
			if(rightmin<node->data)
			{
				return false;
			}
			else
			{
				max=rightmax;
			}
		}
	}
	return true;
}

Node* MakeSearchTree(int* begin, int* end)
{
	if(begin==end)
	{
		Node* node = new Node();
		node->data = *begin;
		return node;
	}
	if(begin<end)
	{
		int* mid = begin + (end-begin)/2;
		Node* node = new Node();
		node->data = *mid;
		if((mid-1)>=begin)
		{
			node->leftchild = MakeSearchTree(begin,mid-1);
		}
		if((mid+1)<=end)
		{
			node->rightchild = MakeSearchTree(mid+1,end);
		}
		return node;
	}
	
}