Maximum Sum BST in Binary Tree — LeetCode solution

An intuitive way

Hey guys, how are you doing ? :)

In this article, we will learn how to solve one of the Hard problems on LeetCode. Maximum Sum BST in Binary Tree

Don’t miss the implementation video C# at the end ;)

Problem Statement

Given a binary tree, we need to find all Binary Search Tree (BST) subtrees present in it, calculate sum of all node values for each BST subtree and return the maximum among all such sums.

Maximum Sum BST in Binary Tree - LeetCode

What is a Binary Search Tree ?

• It contains no duplicates.
• The left subtree will only contain values that are less than the root node’s value.
• The right subtree will only contain values that are greater than the root node’s value.

Sample BST

The Approach

This could be solved using DFS traversal with additional and necessary information along with the return value from a node.

For one particular node or subtree in the given tree, we must come up with a bunch of useful information called state of a node. To derive the current state of a node, we need to know the state of left and right subtree. The state of a node or a subtree includes several information that will help us to decide on further.

The state of a node or subtree includes

• is_bst — a boolean indicates whether the subtree is a binary search tree
• minimum — minimum value ever occurred in the subtree
• maximum— maximum value ever occurred in the subtree
• sum — sum of all node values of the subtree

Using the above state information for left and right subtrees, we need to calculate and keep track of maximum sum occurred so far and also create a state information to be returned to its parent.

Let’s go through the nature of state information for each binary tree based on the situation as below.

State of “One node” binary tree

A tree has only one node. In this case return,

return (true,      // single node is a BST
        node.val,  // minimum value ever occurred is itself
        node.val,  // maximum value ever occurred is itself
        node.val); // the sum is itself

I prefered to choose a tuple rather than a new type called “SubtreeState” or “NodeState” or simply “State” or “Output”. You name it.

State of “Three nodes” binary tree (root, left and right)

As per the root node, the left and right children are “One node” binary trees only if not null. If any child is null, we need to have a constant state which helps parent node to decide accurately.

If the left child is null, then its constant state is

// default state
var (left_is_bst, left_minimum, left_maximum, left_sum) = 
    (true, node.val, node.val - 1, 0);

If not null then recur and get appropriate result.

// If not null, recur and get appropriate result
if (node.left != null) {
    (left_is_bst, left_minimum, left_maximum, left_sum) = 
        recur(node.left);
}

And if the right child is null,

// default state
var (right_is_bst, right_minimum, right_maximum, right_sum) = 
    (true, node.val + 1, node.val, 0);

If not null then recur and get appropriate result.

// If not null, recur and get appropriate result
if (node.right != null) {
    (right_is_bst, right_minimum, right_maximum, right_sum) = 
        recur(node.right);
}

You might notice that we set left child maximum to current node’s value minus 1.

This is to ensure the properties of BST if left or right child is null.

Same applies to right child, we set its minimum to current node’s value plus 1.

Now we have states ready for left and right subtrees. We need to check the following things and construct the current node state.

Constructing the current node’s state

Is current node a BST?

var this_is_bst = left_is_bst 
               && right_is_bst 
               && node.val > left_maximum
               && node.val < right_minimum

• Both left and right subtrees must be a BST.
• The overall maximum of left subtree must be less than current node’s value.
• The overall minimum of right subtree must be greater than current node’s value.

Current node’s overall Maximum

cur_maximum = Math.Max(right_maximum, node.val)

Current node’s overall Minimum

cur_minimum = Math.Min(left_minimum, node.val)

Current node’s Sum

cur_sum = left_sum + right_sum + node.val;

We have constructed the return value for the current node as below.

var cur_state = (this_is_bst, Math.Min(left_maximum, node.val),
                     Math.Max(right_minimum, node.val), sum);                                                       

Before returning this, it is very important to update the variable which holds the maximum sum found so far. We’ll do this in two places.

First, if a node is a leaf node and its value is greater than the maximum sum found so far, then update it. Because leaf node is considered as “One node” binary tree and is a BST too.

Second, If we found that current node is a BST, then update its sum to the maximum sum found so far.

if (this_is_bst) 
    max_sum_so_far = Math.Max(max_sum_so_far, sum);
return cur_state;

The Intuition

So, the intuition here is we have to keep track of Left Maximum and Right Minimum in order to decide whether the current node’s value is as per BST properties. Along with that we also get whether left or right itself a BST and their sums.

Implementation video

Check out the video below for hands on implementation in C#.

Happy solving

Cheers 😉. Follow for more like this.