Largest Binary Search Tree | Maximum Sum BST in Binary Tree | Leetcode

Trees | Binary Search Tree | Data Structure and Algorithm | 180daysofcode #dsa #datastructures #leetcode

00:00 Introduction
00:53 Problem 1 - Largest BST
7:27 Optimized Approach of Problem 1 - Largest BST(Order(n))
49:49 Code Part - Largest BST
1:04:12 Code Part - Method 2 - Largest BST
1:16:28 Problem 2 - Maximum Sum BST in Binary Tree/Home Work
1:18:28 Last Note

Day 170/180, #180daysofcode #180 hard

We are doing 180 days challenge and going to complete the whole course within the duration with quality content on Youtube. I am on the mission to create a tech revolution in our country and in upcoming future we want to create a tech which will create many jobs in India.

Video will come on Mon-Fri at 6am in the morning

DSA Course for free
C++ Free Course
Rohit Negi DSA Course C++
Coder Army DSA Course c++
Function in C++
Pointers in C++.
Strings
Vector
Introduction to Recursion

[CoderArmy]

Binary Search Tree Ends Here, Like Count = 500 karwa do aap log

[abhijeetbasfore]

Problem 2:
class Container{
public:
bool isBST;
int size, mini, maxi;
Container(int data){
isBST = 1;
size = data;
mini = maxi = data;
}
};

class Solution {
private:
Container* findLargestBST(TreeNode* root, int &totalSize)
{
// leaf
if(root->left == nullptr && root->right == nullptr)
{
totalSize = max(totalSize, root->val);
return new Container(root->val);
}
// Only left exist
if(root->left != nullptr && root->right == nullptr){
Container* head = findLargestBST(root->left, totalSize);
if(head->isBST && head->maxi < root->val){
head->size += root->val;
head->maxi = root->val;
totalSize = max(totalSize, head->size);
}
else{
head->isBST = false;
}
return head;
}
// Only right exist
if(root->left == nullptr && root->right != nullptr)
{
Container* head = findLargestBST(root->right, totalSize);
if(head->isBST && head->mini > root->val){
head->size+= root->val;
head->mini = root->val;
totalSize = max(head->size, totalSize);
}
else{
head->isBST = false;
}
return head;
}
// Both left and right exist
else{
Container* leftSub = findLargestBST(root->left, totalSize);
Container* rightSub = findLargestBST(root->right, totalSize);
if(leftSub->isBST && rightSub->isBST && leftSub->maxi < root->val && rightSub->mini > root->val){
Container* head = new Container(root->val);
head->size += leftSub->size + rightSub->size;
head->mini = leftSub->mini;
head->maxi = rightSub->maxi;
totalSize = max(totalSize, head->size);
return head;
}
else{
leftSub->isBST = 0;
return leftSub;
}
}
}
public:
int maxSumBST(TreeNode* root) {
int maxSum = 0;
findLargestBST(root, maxSum);
return maxSum;
}
};

[allinonemoviesyt]

1:18:24 Homework :

class Box{
public:
int sum, min, max;
bool BST;

Box(){
BST = true;
sum = 0;
min = INT_MAX;
max = INT_MIN;
}
};

class Solution {
public:


Box* find(TreeNode* root, int &sum){
if(!root) return new Box();

Box* left = find(root->left, sum);
Box* right = find(root->right, sum);

if(left->BST && right->BST && left->max < root->val && right->min > root->val){
left->sum += right->sum+root->val;
sum = max(sum, left->sum);
left->max = right->max;
if(left->max == INT_MIN) left->max = root->val;
if(left->min == INT_MAX) left->min = root->val;
return left;
}
else{
left->BST = false;
return left;
}
}
int maxSumBST(TreeNode* root) {
int sum = 0;
find(root, sum);
return sum;
}
};

[shreyanshsingh]

I Studied Trees from 2-3 places but I can confidently say that this is the best out of them!!!

[vijaysingh-npj]

गुरु की महिमा का क्या कहें बयान,
उनसे ही मिलता है ज्ञान का वरदान।
बनाते हैं वो हर मुश्किल राह आसान,
उनके बिना अधूरा है जीवन का अरमान। ❤

[tusharkumargupta]

Problem -2 solution

class Box{
public:
bool Bst;
int sum;
int max, min;
public:
Box(){
Bst=1;
sum=0;
min=INT_MAX;
max=INT_MIN;

}
};
class Solution {
public:
Box* find(TreeNode *root, int &totalSum){
if(!root)
return new Box();
else{
Box*leftHead=find(root->left, totalSum);
Box*rightHead=find(root->right, totalSum);
if(leftHead->Bst && rightHead->Bst && leftHead->max<root->val && rightHead->min>root->val )
{
Box*head=new Box();

head->min=min(root->val, leftHead->min);
head->max=max(root->val, rightHead->max);
totalSum=max(totalSum, head->sum);
return head;

}else{
leftHead->Bst=0;
return leftHead;
}
}
}
public:
int maxSumBST(TreeNode* root) {
int totalSum=0;
find(root, totalSum);
return totalSum;
}
};

[xlr-Ujjwal]

Maximum Sum BST in Binary Tree:
class Box {
public:

bool IsBST;
int sum;
int Max, Min;

Box() {

IsBST = true;
sum = 0;
Min = INT_MAX;
Max = INT_MIN;
}
};

class Solution {
public:

Box *Find(TreeNode *root, int &totalSum) {

// If root doesn't exist
if(!root) {
return new Box();
}

// If root exist
else {

Box *leftHead = Find(root ->left, totalSum);
Box *rightHead = Find(root ->right, totalSum);

Box *head = new Box();

if(leftHead ->IsBST && rightHead ->IsBST && leftHead ->Max < root ->val && rightHead ->Min > root ->val) {

head ->sum = root ->val + leftHead ->sum + rightHead ->sum;
head ->Min = min(leftHead ->Min, root ->val);
head ->Max = max(rightHead ->Max, root ->val);
totalSum = max(totalSum, head ->sum);

return head;
}
else {
head ->IsBST = false;
return head;
}
}
}

int maxSumBST(TreeNode* root) {

int totalSum = 0;

Find(root, totalSum);

return totalSum;
}
};

[fachoyt]

Zindagi Itni Khubsurat Na Hoti
Agr Aap Jaise Sir Nahi Milte.. ❣

[VinuSawant-zk]

Thank you Bhaiya Itna Achcha Dsa Content Dene Ke Liye❤️

[kkjhajaisitola]

Maximum Sum BST in Binary Tree:
class Box {
public:
bool bst;
int sum, Min, Max;
Box() {
bst = 1;
sum = 0;
Min = INT_MAX;
Max = INT_MIN;
}
};
Box* find(TreeNode* root, int& totalsum) {
if (!root)
return new Box();
Box* lefthand = find(root->left, totalsum);
Box* righthand = find(root->right, totalsum);
if (lefthand->bst && righthand->bst && lefthand->Max < root->val &&
righthand->Min > root->val) {
Box* head = new Box();
head->sum = root->val + lefthand->sum + righthand->sum;
head->Min = min(lefthand->Min, root->val);
head->Max = max(righthand->Max, root->val);
totalsum = max(totalsum, head->sum);
return head;
} else {
lefthand->bst = 0;
return lefthand;
}
}
int maxSumBST(TreeNode* root) {
int totalsum = 0;
find(root, totalsum);
return totalsum;
}

[Anubhav_Raj]

Largest Sum BST code of Leetcode question


class Box
{
public:
bool BST;
int sum;
int min, max;

Box()
{
BST=1;
sum=0;
min=INT_MAX;
max=INT_MIN;
}
};
class Solution {
public:

Box*find(TreeNode*root, int &Totalsum)
{
//root doesm't exits
if(!root)
return new Box();


//root exists
Box* lefthead=find(root->left, Totalsum);
Box* righthead=find(root->right, Totalsum);

//BST EXISTS

{
Box* head=new Box();

head->min=min(root->val, lefthead->min);
head->max=max(root->val, righthead->max);

Totalsum=max(Totalsum, head->sum);
return head;
}
else
{
lefthead->BST=0;
return lefthead;
}
}
int maxSumBST(TreeNode* root)
{
int Totalsum=0;
find(root, Totalsum);
return Totalsum;
}

[Vardanaggarwal]

class Box
{
public:
bool BST;
int sum;
int max;
int min;


Box(int data)
{
BST = 1;
sum = data;
min = data;
max = data;
}
};
class Solution {
public:
Box *find(TreeNode *root, int &totalsum)
{
// leaf node
if(!root->left && !root->right)
{
Box *head = new Box(root->val);

totalsum = max(totalsum, head->sum);
return head;
}
// only right side exist
else if(!root->left && root->right)
{
Box *head = find(root->right, totalsum);

if(head->BST && head->min > root->val)
{
head->sum += root-> val;
head->min = root->val;
totalsum = max(totalsum, head->sum);
return head;
}
else
{
head->BST = 0;
return head;
}
}
// only left side exist
else if(root->left && !root->right)
{
Box *head = find(root->left, totalsum);

if(head->BST && head->max < root->val)
{
head->sum += root-> val;
head->max = root->val;
totalsum = max(totalsum, head->sum);
return head;
}
else
{
head->BST = 0;
return head;
}
}
// both side exists
else
{
Box *lefthead = find(root->left, totalsum);
Box *righthead = find(root->right, totalsum);

if(lefthead->BST && righthead->BST && lefthead->max < root->val && righthead->min > root->val)
{
Box *head = new Box(root->val);
head->sum += lefthead->sum + righthead->sum;
head->min = lefthead->min;
head->max = righthead->max;
totalsum = max(totalsum, head->sum);
return head;
}
else
{
lefthead->BST = 0;
return lefthead;
}
}
}
int maxSumBST(TreeNode* root) {
int totalsum = 0;
find(root, totalsum);

return totalsum;
}
};
// finally bhaiya last homework question done with similar approach with little changes and bhaiya very very thanks for this amazing series.

[asad_iliyas]

H/W =
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/

class Box{

public:

bool BST;
int sum;
int min, max;

Box(int data){
BST = 1;
sum = data;
min = INT_MAX;
max = INT_MIN;
}

};

class Solution {
public:

Box* find(TreeNode *root, int &totalsum){

if(!root)//Root doesn't exist
return new Box(0);


Box* lefthead = find(root->left, totalsum);
Box* righthead = find(root->right, totalsum);

if(lefthead->BST && righthead->BST && lefthead->max<root->val && righthead->min>root->val){

Box* head = new Box(root->val);
head->sum += lefthead->sum + righthead->sum;
head->min=min(lefthead->min, root->val);
head->max=max(righthead->max, root->val);
totalsum = max(totalsum, head->sum);
return head;
}
else
{
lefthead->BST = 0;
return lefthead;
}

}

int maxSumBST(TreeNode* root) {
int totalsum = 0;
find(root, totalsum);
return totalsum;
}
};

[chiragvarshney]

Thankyou bhaiya very much... this dsa series is mind blowing🔥🔥🔥

[dhakadkumman]

class Box
{
public :
bool BST;
int sum;
int min;
int max;
Box()
{
BST = 1;
sum = 0;
min = INT_MAX;
max = INT_MIN;
}
};

class Solution {
public:
Box* find(TreeNode * root, int &totalSum)
{
if(root == NULL)
return new Box();
Box* leftHead = find(root->left, totalSum);
Box* rightHead = find(root->right, totalSum);
if(leftHead->BST && rightHead->BST && leftHead->max < root->val && rightHead->min > root->val)
{
Box* head = new Box();
head->sum = leftHead->sum + rightHead->sum + root->val;
head->min = min(leftHead->min, root->val);
head->max = max(rightHead->max, root->val);
totalSum = max(totalSum, head->sum);
return head;
}
leftHead->BST = 0;
return leftHead;

}
int maxSumBST(TreeNode* root) {
int totalSum = 0;
find(root, totalSum);
return totalSum;
}
};

[DhanushAg-shqp]

this series is very useful to us (jai ho bhaiya )

[suheb_tech]

Simple solution of Problem 2:
class Box
{
public:
bool BST;
int sum;
int min, max;
Box()
{
BST = 1;
sum = 0;
min = INT_MAX;
max = INT_MIN;
}

};
class Solution {
public:
Box * find(TreeNode* root, int &totalsum)
{
// root doesn't exist
if(!root)
{
return new Box();
}
// root exist
Box* lefthead = find(root->left, totalsum);
Box* righthead = find(root->right, totalsum);


{
Box * head = new Box();
head->sum =
head->min = min(root->val, lefthead->min);
head->max = max(root->val, righthead->max);
totalsum = max(totalsum, head->sum);
return head;
}
else
{
lefthead->BST = 0;
return lefthead;
}
}
int maxSumBST(TreeNode* root)
{
int totalsum =0;
find(root, totalsum);
return totalsum;

}
};

[manish_kumar_iitg]

optimized solution for problem 2:-


class box{
public:
bool BST;
int sum;
int mini, maxi;
box(){
BST = 1;
sum = 0;
mini = INT_MAX;
maxi = INT_MIN;
}
};
class Solution {
public:
box *solve(TreeNode* root, int &ans){
if(!root){
return new box();
}
box *l = solve(root->left, ans);
box *r = solve(root->right, ans);
if(l->BST&&r->BST&&l->maxi < root->val && r->mini > root->val){
box *head = new box();
head->BST = true;
head->sum = root->val + l->sum + r->sum;
head->mini = min(root->val, l->mini);
head->maxi = max(root->val, r->maxi);
ans = max(ans, head->sum);
return head;
}
l->BST = false;
return l;

}
int maxSumBST(TreeNode* root) {
int ans = 0;
solve(root, ans);
return ans;
}
};

[RJFF-rw]

Bruteforce method of 1st problem:
class Solution{
public:
/*You are required to complete this method */
// Return the size of the largest sub-tree which is also a BST
int getSize(Node *root) {
if(!root)
return 0;

return
}
bool checkBST(Node *root) {
int prev=-1;
return BST(root, prev);
}
bool BST(Node *root, int &prev) {//verify using in order traversal
if(!root)
return 1;

int l=BST(root->left, prev);
if(l==0)
return 0;

if(root->data <= prev)
return 0;

prev=root->data;

return BST(root->right, prev);
}
void calculate(Node *root, int &totalsize) {
if(!root)
return;

if(checkBST(root)) {
totalsize=max(totalsize, getSize(root));
}
calculate(root->left, totalsize);
calculate(root->right, totalsize);
}
int largestBst(Node *root)
{
//Your code here
int totalsize=0;
calculate(root, totalsize);
return totalsize;
}
};

[Vardanaggarwal]

BHAIYA REALLY MAZAA AA GYA IS SERIES MAI.