Skip to main content

find largest binary search tree in a Binary Tree

We have to write a program to find the largest binary search tree (BST) in a given binary tree.

A given tree is BST if the value of node is greater than the value of its left child and smaller than the value of its right child.

We will use top-down approach for solving this. We will traverse the whole tree. At every node we will check if the subtree is BST or not. If the current tree is BST then we found the largest BST. If not, then we  have to check the whether left or right subtree is BST or not. If only one tree is BST then we will return that subtree. If both left and right subtrees are BST, then we will return the larger of the two.

Example:
                                             60
                                         /         \
                                     50           90
                                  /      \        /      \
                               40     55    70     100
                                                /         /     \
                                             80      200  150

In the above binary tree, the whole tree is not BST because left child of 70 is 80 (>70) and also left child of 100 is 200 (>100). 

Largest BST in the above example is:
                             50
                           /     \
                         40     55

The code will return 3 as there are three nodes in the largest BST. 

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// C++ program to find largest binary search tree in a Binary Tree
#include<bits/stdc++.h>
using namespace std;
class node{ 
public: 
int data;
node* left;
node* right;
node(int data) // Constructor that makes a new node
this->data = data;
this->left = NULL;
this->right = NULL;
}
};

// This function finds the maximum size of the largest BST.
// If the tree is BST then this function returns the size of the tree
int findBST(node* node, int *minn, int *maxx, int *maxSize, bool *isBst){
// Base Case
if(node == NULL){
*isBst = 1;
return 0;
}
int lSize, rSize; // Stores the size of left and right subtree.
int mi = INT_MAX;
bool flag1 = 0; // Flag for left subtree. It stores 1 if left subtree is BST.
bool flag2 = 0; // Flag for right subtree. It stores 1 if right subtree is BST.
*maxx = INT_MIN; 
lSize = findBST(node->left, minn, maxx, maxSize, isBst); // recursive call for left subtree
// checking if left subtree is BST or not
if (*isBst == 1 and node->data > *maxx) 
flag1 = 1;
mi = *minn;
*minn = INT_MAX;
rSize = findBST(node->right, minn, maxx, maxSize, isBst); // recursive call right subtree
// checking if right subtree is BST or not
if (*isBst == 1 and node->data < *minn) 
flag2 = 1;
if (mi < *minn)
*minn = mi;
if (node->data < *minn)
*minn = node->data;
if (node->data > *maxx)
*maxx = node->data;
// If right and left subtrees are BST, then return the size of the tree.
if(flag1 and flag2){ 
if (lSize + rSize + 1 > *maxSize) 
*maxSize = lSize + rSize + 1; 
return lSize + rSize + 1; 
}
else{ 
// If tree is not BST
*isBst = 0;
return 0;
}
int main()
{
node *root = new node(60);
root->left = new node(50);
root->right = new node(90);
root->left->left = new node(40);
root->left->right = new node(55);
root->right->left = new node(70);
root->right->left->left = new node(80);
root->right->right = new node(100);
root->right->right->left = new node(200);
root->right->right->right = new node(150);
int minn = INT_MAX, maxx = INT_MIN;
int maxSize = 0; // stores maximum size of the BST
bool isBst = 0; // If tree is BST then we store 1 in it, otherwise 0.
findBST(root, &minn, &maxx, &maxSize, &isBst); // values are passed by reference
cout<<"Size of the largest BST is: "<<maxSize;
return 0;
}
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Output : 3

Time Complexity : O(n)
n is the number of nodes in  the given binary tree

Popular posts from this blog

Introduction to Java Security

Introduction to Java Security The Java security architecture includes a large set of application programming interfaces (APIs), tools, and implementations of commonly-used security algorithms, mechanisms, and protocols. The Java security APIs span a wide range of areas. Cryptographic and public key infrastructure (PKI) interfaces provide the underlying basis for developing secure applications. Interfaces for performing authentication and access control enable applications to guard against unauthorized access to protected resources. The JDK includes a number of providers that implement a core set of security services. It also allows for additional custom providers to be installed. This enables developers to extend the platform with new security mechanisms. The JDK is divided into modules. Modules that contain security APIs include the following:

Module Description java.base Defines the foundational APIs of Java SE;  contained packages include java.securityjavax.cryptojavax.net.ssl,  and…

SQL Injection

Overview A SQL injection attack consists of insertion or "injection" of a SQL query via the input data from the client to the application. A successful SQL injection exploit can read sensitive data from the database, modify database data (Insert/Update/Delete), execute administration operations on the database (such as shutdown the DBMS), recover the content of a given file present on the DBMS file system and in some cases issue commands to the operating system. SQL injection attacks are a type of injection attack, in which SQL commands are injected into data-plane input in order to effect the execution of predefined SQL commands. Threat ModelingSQL injection attacks allow attackers to spoof identity, tamper with existing data, cause repudiation issues such as voiding transactions or changing balances, allow the complete disclosure of all data on the system, destroy the data or make it otherwise unavailable, and become administrators of the database server.SQL Injection is ve…

Insertion Node in the Linkelist.

In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1) At the front of the linked list
2) After a given node.
3) At the end of the linked list
public class Linkedlist { Node head; class Node{ int data; Node next; Node(int d){ data =d; next=null; } } // INSERT THE NODE AT THE BEGIN OF LINKEDLIST. public void insertAtfront(int new_data){ // Node temp = head; Node new_node = new Node(new_data); new_node.next = head; head = new_node; }  // INSERT THE NODE AT THE GIVEN POSITION IN LINKEDLIST.
public void insertAtGiven(Node prev_node,int new_data) { if(prev_node == null){ System.out.print("previous node can't be null"); return; } Node new_node = new Node(new_data); new_node.next = prev_node.next; prev_node.next = new_node; } // INSERT THE NODE  AT THE END OF THE LINKEDLIST.   public void insertAtEnd(int new_data){ Node new_node = new Node(new_data); new_node.nex…