Largest Binary Search Tree (BST) in a Binary Tree

Source

Problem

Given a binary tree, find the largest Binary Search Tree (BST), where largest means BST with largest number of nodes in it. The largest BST may or may not include all of its descendants.

My Attempt

Every node in the BST will be an BST (Recursive definition of BST)

Go top down. In-order traversal. traversal. If you find a node which does not hav both children which does not follow BST property save them (Add them to linked list) we wil treat them as root of new possible BST,

lbst(node *root, int &count, node* queue) {

ChkPtrAssert(queue);

if (!root) { return; }

// visit the element if atleast one chil has BST property. Include the node in current BST tree

if (root->left && root->left->data <>data) || (root->right && root->right->data >= no)

count++;

//visit left child

if (root->left)

if(root->left->data <>data)

lbst(root->left, count, queue);

else

{

// skip the element and add it to queue. We will visit latter

queue->addQueue(root->left);

}

//visit tight child

if (root->right)

if(root->right->data <>data)

lbst(root->right, count, queue);

else

{

// skip the element and add it to queue. We will visit latter

queue->addQueue(root->left);

}

}

main() {

Queue *queue = new Queue();

Node* lbstRoot = root;

int maxCount = 0;

ChkMem(queue);

queue->addQueue(root);

node* currentNode = root;

while (CurrentNode)

{

lbst(currentNode, count, queue);

if (count > maxCount) {

maxCount = count;

lbstRoot = currentNode;

}

queue->popQueue(&currentNode);

}