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

Last Updated : 06 Aug, 2021

Given a binary tree, the task is to print the maximum sum of nodes of a sub-tree which is also a Binary Search Tree.
Examples:

Input : 
       7
      /  \
     12    2
    /  \    \
   11  13    5
  /         / \
 2         1   38  

Output:44
BST rooted under node 5 has the maximum sum
       5
      / \
     1   38

Input:
      5
     /  \
    9    2
   /      \
  6        3
 / \
8   7   

Output: 8
Here each leaf node represents a binary search tree 
also a BST with sum 5 exists
     2
      \
       3
But the leaf node 8 has the maximum sum.

Approach: We traverse the tree in bottom-up manner. For every traversed node, we store the information of maximum and minimum of that subtree, a variable isBST to store if it is a BST, variable currmax to store the maximum sum of BST found till now, and a variable sum to store the sum of Left and Right subtree(which is also a BST) rooted under the current node.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Binary tree node
struct Node {
    struct Node* left;
    struct Node* right;
    int data;
 
    Node(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
 
// Information stored in every
// node during bottom up traversal
struct Info {
 
    // Max Value in the subtree
    int max;
 
    // Min value in the subtree
    int min;
 
    // If subtree is BST
    bool isBST;
 
    // Sum of the nodes of the sub-tree
    // rooted under the current node
    int sum;
 
    // Max sum of BST found till now
    int currmax;
};
 
// Returns information about subtree such as
// subtree with maximum sum which is also a BST
Info MaxSumBSTUtil(struct Node* root, int& maxsum)
{
    // Base case
    if (root == NULL)
        return { INT_MIN, INT_MAX, true, 0, 0 };
 
    // If current node is a leaf node then
    // return from the function and store
    // information about the leaf node
    if (root->left == NULL && root->right == NULL) {
        maxsum = max(maxsum, root->data);
        return { root->data, root->data, true, root->data, maxsum };
    }
 
    // Store information about the left subtree
    Info L = MaxSumBSTUtil(root->left, maxsum);
 
    // Store information about the right subtree
    Info R = MaxSumBSTUtil(root->right, maxsum);
 
    Info BST;
 
    // If the subtree rooted under the current node
    // is a BST
    if (L.isBST && R.isBST && L.max < root->data && R.min > root->data) {
 
        BST.max = max(root->data, max(L.max, R.max));
        BST.min = min(root->data, min(L.min, R.min));
 
        maxsum = max(maxsum, R.sum + root->data + L.sum);
        BST.sum = R.sum + root->data + L.sum;
 
        // Update the current maximum sum
        BST.currmax = maxsum;
 
        BST.isBST = true;
        return BST;
    }
 
    // If the whole tree is not a BST then
    // update the current maximum sum
    BST.isBST = false;
    BST.currmax = maxsum;
    BST.sum = R.sum + root->data + L.sum;
 
    return BST;
}
 
// Function to return the maximum
// sum subtree which is also a BST
int MaxSumBST(struct Node* root)
{
    int maxsum = INT_MIN;
    return MaxSumBSTUtil(root, maxsum).currmax;
}
 
// Driver code
int main()
{
    struct Node* root = new Node(5);
    root->left = new Node(14);
    root->right = new Node(3);
    root->left->left = new Node(6);
    root->right->right = new Node(7);
    root->left->left->left = new Node(9);
    root->left->left->right = new Node(1);
 
    cout << MaxSumBST(root);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
// Binary tree node
static class Node 
{
    Node left;
    Node right;
    int data;
 
    Node(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
};
 
// Information stored in every
// node during bottom up traversal
static class Info 
{
 
    // Max Value in the subtree
    int max;
 
    // Min value in the subtree
    int min;
 
    // If subtree is BST
    boolean isBST;
 
    // Sum of the nodes of the sub-tree
    // rooted under the current node
    int sum;
 
    // Max sum of BST found till now
    int currmax;
     
    Info(int m,int mi,boolean is,int su,int cur)
    {
        max = m;
        min = mi;
        isBST = is;
        sum = su;
        currmax = cur;
    }
    Info(){}
};
 
static class INT
{
    int a;
}
 
// Returns information about subtree such as
// subtree with the maximum sum which is also a BST
static Info MaxSumBSTUtil( Node root, INT maxsum)
{
    // Base case
    if (root == null)
        return new Info( Integer.MIN_VALUE, 
                        Integer.MAX_VALUE, true, 0, 0 );
 
    // If current node is a leaf node then
    // return from the function and store
    // information about the leaf node
    if (root.left == null && root.right == null)
    {
        maxsum.a = Math.max(maxsum.a, root.data);
        return new Info( root.data, root.data, 
                        true, root.data, maxsum.a );
    }
 
    // Store information about the left subtree
    Info L = MaxSumBSTUtil(root.left, maxsum);
 
    // Store information about the right subtree
    Info R = MaxSumBSTUtil(root.right, maxsum);
 
    Info BST=new Info();
 
    // If the subtree rooted under the current node
    // is a BST
    if (L.isBST && R.isBST && L.max < root.data && 
                               R.min > root.data)
    {
 
        BST.max = Math.max(root.data, Math.max(L.max, R.max));
        BST.min = Math.min(root.data, Math.min(L.min, R.min));
 
        maxsum.a = Math.max(maxsum.a, R.sum + root.data + L.sum);
        BST.sum = R.sum + root.data + L.sum;
 
        // Update the current maximum sum
        BST.currmax = maxsum.a;
 
        BST.isBST = true;
        return BST;
    }
 
    // If the whole tree is not a BST then
    // update the current maximum sum
    BST.isBST = false;
    BST.currmax = maxsum.a;
    BST.sum = R.sum + root.data + L.sum;
 
    return BST;
}
 
// Function to return the maximum
// sum subtree which is also a BST
static int MaxSumBST( Node root)
{
    INT maxsum = new INT();
    maxsum.a = Integer.MIN_VALUE;
    return MaxSumBSTUtil(root, maxsum).currmax;
}
 
// Driver code
public static void main(String args[])
{
    Node root = new Node(5);
    root.left = new Node(14);
    root.right = new Node(3);
    root.left.left = new Node(6);
    root.right.right = new Node(7);
    root.left.left.left = new Node(9);
    root.left.left.right = new Node(1);
 
    System.out.println( MaxSumBST(root));
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of 
# the above approach
from sys import maxsize as INT_MAX
INT_MIN = -INT_MAX
 
# Binary tree node
class Node:
   
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Information stored in every
# node during bottom up traversal
class Info:
   
    def __init__(self, _max, _min, 
                 isBST, _sum, currmax):
       
        # Max Value in the subtree
        self.max = _max
 
        # Min value in the subtree
        self.min = _min
 
        # If subtree is BST
        self.isBST = isBST
 
        # Sum of the nodes of the sub-tree
        # rooted under the current node
        self.sum = _sum
 
        # Max sum of BST found till now
        self.currmax = currmax
 
# Returns information about 
# subtree such as subtree 
# with maximum sum which 
# is also a BST
def MaxSumBSTUtil(root: Node) -> Info:
    global maxsum
 
    # Base case
    if (root is None):
        return Info(INT_MIN, INT_MAX, 
                    True, 0, 0)
 
    # If current node is a 
    # leaf node then return 
    # from the function and store
    # information about the leaf node
    if (root.left is None and
        root.right is None):
        maxsum = max(maxsum, 
                     root.data)
        return Info(root.data, root.data, 
                    True, root.data, maxsum)
 
    # Store information about 
    # the left subtree
    L = MaxSumBSTUtil(root.left)
 
    # Store information about 
    # the right subtree
    R = MaxSumBSTUtil(root.right)
 
    BST = Info
 
    # If the subtree rooted under 
    # the current node is a BST
    if (L.isBST and R.isBST and
        L.max < root.data and
        R.min > root.data):
 
        BST.max = max(root.data, 
                  max(L.max, R.max))
        BST.min = min(root.data, 
                  min(L.min, R.min))
 
        maxsum = max(maxsum, R.sum +
                     root.data + L.sum)
        BST.sum = R.sum + root.data + L.sum
 
        # Update the current maximum sum
        BST.currmax = maxsum
 
        BST.isBST = True
        return BST
 
    # If the whole tree is not 
    # a BST then update the 
    # current maximum sum
    BST.isBST = False
    BST.currmax = maxsum
    BST.sum = R.sum + root.data + L.sum
 
    return BST
 
# Function to return the maximum
# sum subtree which is also a BST
def MaxSumBST(root: Node) -> int:
    global maxsum
    return MaxSumBSTUtil(root).currmax
 
# Driver code
if __name__ == "__main__":
 
    root = Node(5)
    root.left = Node(14)
    root.right = Node(3)
    root.left.left = Node(6)
    root.right.right = Node(7)
    root.left.left.left = Node(9)
    root.left.left.right = Node(1)
 
    maxsum = INT_MIN
    print(MaxSumBST(root))
 
# This code is contributed by sanjeev2552

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
// Binary tree node
public class Node 
{
    public Node left;
    public Node right;
    public int data;
 
    public Node(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
};
 
// Information stored in every
// node during bottom up traversal
public class Info 
{
 
    // Max Value in the subtree
    public int max;
 
    // Min value in the subtree
    public int min;
 
    // If subtree is BST
    public bool isBST;
 
    // Sum of the nodes of the sub-tree
    // rooted under the current node
    public int sum;
 
    // Max sum of BST found till now
    public int currmax;
     
    public Info(int m,int mi,bool s,int su,int cur)
    {
        max = m;
        min = mi;
        isBST = s;
        sum = su;
        currmax = cur;
    }
    public Info(){}
};
 
public class INT
{
    public int a;
}
 
// Returns information about subtree such as
// subtree with the maximum sum which is also a BST
static Info MaxSumBSTUtil( Node root, INT maxsum)
{
    // Base case
    if (root == null)
        return new Info( int.MinValue, 
                        int.MaxValue, true, 0, 0 );
 
    // If current node is a leaf node then
    // return from the function and store
    // information about the leaf node
    if (root.left == null && root.right == null)
    {
        maxsum.a = Math.Max(maxsum.a, root.data);
        return new Info( root.data, root.data, 
                        true, root.data, maxsum.a );
    }
 
    // Store information about the left subtree
    Info L = MaxSumBSTUtil(root.left, maxsum);
 
    // Store information about the right subtree
    Info R = MaxSumBSTUtil(root.right, maxsum);
 
    Info BST = new Info();
 
    // If the subtree rooted under the current node
    // is a BST
    if (L.isBST && R.isBST && L.max < root.data && 
                            R.min > root.data)
    {
 
        BST.max = Math.Max(root.data, Math.Max(L.max, R.max));
        BST.min = Math.Min(root.data, Math.Min(L.min, R.min));
 
        maxsum.a = Math.Max(maxsum.a, R.sum + root.data + L.sum);
        BST.sum = R.sum + root.data + L.sum;
 
        // Update the current maximum sum
        BST.currmax = maxsum.a;
 
        BST.isBST = true;
        return BST;
    }
 
    // If the whole tree is not a BST then
    // update the current maximum sum
    BST.isBST = false;
    BST.currmax = maxsum.a;
    BST.sum = R.sum + root.data + L.sum;
 
    return BST;
}
 
// Function to return the maximum
// sum subtree which is also a BST
static int MaxSumBST( Node root)
{
    INT maxsum = new INT();
    maxsum.a = int.MinValue;
    return MaxSumBSTUtil(root, maxsum).currmax;
}
 
// Driver code
public static void Main(String []args)
{
    Node root = new Node(5);
    root.left = new Node(14);
    root.right = new Node(3);
    root.left.left = new Node(6);
    root.right.right = new Node(7);
    root.left.left.left = new Node(9);
    root.left.left.right = new Node(1);
 
    Console.WriteLine( MaxSumBST(root));
}
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of the approach
     
// Binary tree node
class Node 
{
    constructor(data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
};
 
// Information stored in every
// node during bottom up traversal
class Info 
{
     
    constructor(m,mi,s,su,cur)
    {
        // max Value in the subtree
        this.max = m;
        // min value in the subtree
        this.min = mi;
        // If subtree is BST
        this.isBST = s;
        // Sum of the nodes of the sub-tree
        // rooted under the current node
        this.sum = su;
        // max sum of BST found till now
        this.currmax = cur;
    }
};
 
class INT
{
    constructor()
    {
        this.a = 0;
    }
}
 
// Returns information about subtree such as
// subtree with the maximum sum which is also a BST
function MaxSumBSTUtil( root, maxsum)
{
    // Base case
    if (root == null)
        return new Info( -1000000000, 
                        1000000000, true, 0, 0 );
 
    // If current node is a leaf node then
    // return from the function and store
    // information about the leaf node
    if (root.left == null && root.right == null)
    {
        maxsum.a = Math.max(maxsum.a, root.data);
        return new Info( root.data, root.data, 
                        true, root.data, maxsum.a );
    }
 
    // Store information about the left subtree
    var L = MaxSumBSTUtil(root.left, maxsum);
 
    // Store information about the right subtree
    var R = MaxSumBSTUtil(root.right, maxsum);
 
    var BST = new Info();
 
    // If the subtree rooted under the current node
    // is a BST
    if (L.isBST && R.isBST && L.max < root.data && 
                            R.min > root.data)
    {
 
        BST.max = Math.max(root.data, Math.max(L.max, R.max));
        BST.min = Math.min(root.data, Math.min(L.min, R.min));
 
        maxsum.a = Math.max(maxsum.a, R.sum + root.data + L.sum);
        BST.sum = R.sum + root.data + L.sum;
 
        // Update the current maximum sum
        BST.currmax = maxsum.a;
 
        BST.isBST = true;
        return BST;
    }
 
    // If the whole tree is not a BST then
    // update the current maximum sum
    BST.isBST = false;
    BST.currmax = maxsum.a;
    BST.sum = R.sum + root.data + L.sum;
 
    return BST;
}
 
// Function to return the maximum
// sum subtree which is also a BST
function MaxSumBST( root)
{
    var maxsum = new INT();
    maxsum.a = -1000000000;
    return MaxSumBSTUtil(root, maxsum).currmax;
}
 
// Driver code
var root = new Node(5);
root.left = new Node(14);
root.right = new Node(3);
root.left.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(9);
root.left.left.right = new Node(1);
document.write( MaxSumBST(root));
 
// This code is contributed by itsok.
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

Sakshi_Srivastava

Improve

Find the minimum Sub-tree with target sum in a Binary search tree

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

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?