Find Maximum Size BST in Binary Tree

#include
#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct BinaryTree
{
int data;
struct BinaryTree * left;
struct BinaryTree * right;
};


// Find the largest BST subtree in a binary tree.
// If the subtree is a BST, return total number of nodes.
// If the subtree is not a BST, -1 is returned.
int findLargestBSTSubtree(struct BinaryTree *p, int &min, int &max,int &maxNodes, struct BinaryTree* &largestBST)
{
if (!p) return 0;
bool isBST = true;
int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, largestBST);
int currMin = (leftNodes == 0) ? p->data : min;
if (leftNodes == -1 ||
(leftNodes != 0 && p->data <= max))
isBST = false;
int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, largestBST);
int currMax = (rightNodes == 0) ? p->data : max;
if (rightNodes == -1 ||
(rightNodes != 0 && p->data >= min))
isBST = false;
if (isBST) {
min = currMin;
max = currMax;
int totalNodes = leftNodes + rightNodes + 1;
if (totalNodes > maxNodes) {
maxNodes = totalNodes;
largestBST = p;
}
return totalNodes;
} else {
return -1; // This subtree is not a BST
}
}


/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct BinaryTree* newNode(int data)
{
struct BinaryTree* node = (struct BinaryTree*)
malloc(sizeof(struct BinaryTree));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

struct BinaryTree* findLargestBST(struct BinaryTree *root) {
struct BinaryTree *largestBST = NULL;
int min=INT_MAX, max=INT_MIN;
int maxNodes = INT_MIN;
findLargestBSTSubtree(root, &min, &max, &maxNodes, &largestBST);
return largestBST;
}

void print(struct BinaryTree *root)
{
if(root==NULL)
return ;

print(root->left);
printf("%d ",root->data);
print(root->right);

}

int main()
{

struct BinaryTree* root = newnode(10);
root->left = newnode(5);
root->right = newnode(15);
root->left->left = newnode(1);
root->left->right = newnode(8);
root->right->right =newnode(7);

struct BinaryTree* tmp=findLargestBST(root);

print(tmp);
return 0;

}

Time Complexity O(n)