Advertisement
imashutosh51

Maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST

Jul 25th, 2022 (edited)
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. /*Problem : Maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST
  2. Logic is : make a function which will return maxium maximum,minimum,sum,binary_tree_or_not.
  3. so,if root->data is lesser than all nodes of right subtree ie. root->data < min(right_subtree) and root->data is greater than maximum of left subtree ie. root->data>max(left_subtree) than the subtree with root is BST.
  4. our function will return max,min and subtree sum for the subtrees and when we find somenode satisfying the BST condition and that subtree sum is greater than the sum of our current maxium sum which we carry using call by reference than we update the output ie.ans.
  5. */
  6.  
  7. struct _data{
  8.     int sum,_min,_max;
  9.     bool is_bst;
  10. };
  11. _data fun(TreeNode *root,int &ans){
  12.     if(!root->left && !root->right){
  13.         ans=max(ans,root->val);
  14.         _data temp;
  15.         temp.is_bst=true;
  16.         temp.sum=root->val;
  17.         temp._max=root->val;
  18.         temp._min=root->val;
  19.         return temp;
  20.     }
  21.     _data left,right;
  22.     left.is_bst=true;left.sum=0;left._min=INT_MAX,left._max=INT_MIN;
  23.     right.is_bst=true;right.sum=0;right._min=INT_MAX,right._max=INT_MIN;
  24.    
  25.     if(root->left) left=fun(root->left,ans);
  26.     if(root->right) right=fun(root->right,ans);
  27.     if(left.is_bst && right.is_bst && left._max<root->val && right._min>root->val ){
  28.        
  29.         ans=max(ans,left.sum+right.sum+root->val);
  30.         left._max=max(max(left._max,right._max),root->val);
  31.         left._min=min(min(left._min,right._min),root->val);
  32.         left.sum=left.sum+right.sum+root->val;
  33.         return left;
  34.     }
  35.     else{
  36.         left.is_bst=false;
  37.         return left;
  38.     }
  39. }
  40.  
  41. class Solution {
  42. public:
  43.     int maxSumBST(TreeNode* root) {
  44.        if(!root) return 0;
  45.        int ans=0;
  46.        fun(root,ans);
  47.        return ans;  
  48.     }
  49. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement