Maximum Sum BST in a Binary Tree

Question

I was trying to find the Maximum sum BST of a binary tree on LeetCode. While the Java code I have come up with, mostly seems right and is able to pass 55 out of the given 59 test cases too, the error of 'Time Limit Exceeded' comes up.

Is there anything I can change, in the same given code, that would optimize it and/or get it accepted?

---

problem statement

1373. Maximum Sum BST in Binary Tree

Given a binary tree root, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

example

Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.

Constraints:
The number of nodes in the tree is in the range [1, 4 * 10⁴].
-4 * 1e⁴ <= Node.val <= 4 * 1e⁴

---

The contest calls Solution.maxSumBST()

class Solution {

    int maxSum = 0;
    int sum = 0;
    TreeNode ansNode = new TreeNode();


    private boolean isBST(TreeNode root, int minVal, int maxVal) {        //To check if a tree is a BST

        if (root==null) {
            return true;
        }

        if (root.val>=maxVal || root.val<=minVal) {
            return false;
        }

        return (isBST(root.left, minVal, root.val) && isBST(root.right, root.val, maxVal));
    }


    private void rootFinder(TreeNode root) {                     //Helper function to find the root of the required BST
        
        if (root==null) {
            return;
        }

        rootFinder(root.left);


        if (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE)) {

            int currSum = sumFinder(root);
            if (currSum > maxSum) {
                maxSum = currSum;
                ansNode = root;
            }
            sum = 0;
        }

        rootFinder(root.right);
    }


    public int maxSumBST(TreeNode root) {

        rootFinder(root);
        return maxSum;
    }


    private int sumFinder (TreeNode root) {          //To find the sum of all the nodes of a tree

        if (root==null) {
            return 0;
        }

        sumFinder(root.left);
        sum = sum + root.val;
        sumFinder(root.right);
        return sum;
    }
}

Answer 1

Beyond method naming and a comment stating what the signature boolean isBST(TreeNode root,…) suggest, the code gives no indication what it is there for, what the methods need to and do accomplish and how:

Document your code. In the code.
With Java, the conventional mechanism is providing doc comments.
maxSum and sum deserve a comment about the extreme values possible.

ansNode is not used. (LeetCode's problem title Maximum Sum BST … is delusory; compare to Maximum BST Sum ….)

Code indentation is consistent.
Use of white space isn't quite: there is a double blank line in rootFinder();
sometimes there are spaces around comparison operators, sometimes not; there is one block statement starting with a blank line. (I prefer to go easier on vertical space: just one blank line between "peer" items such as methods, no blank line following an opening brace.)

In comparisons, especially in multiple related ones, I prefer "expressions arranged in ascending order":
if (root.val <= minVal || maxVal <= root.val) // no BST
(actually, I prefer

        return root == null
               || minVal < root.val && root.val < maxVal
                  && isBST(root.left, minVal, root.val)
                  && isBST(root.right, root.val, maxVal);

) - note this already suffers the "susceptibility" J_H points out as a "point of attack".

sum += root.val; reads add to sum more immediately than sum = sum + ….

Helper function does not add useful information to a private method member; +it rubs me the wrong way with a void method.

There is an untoward interdependency between rootFinder() setting sum to zero and sumFinder() manipulating it. "Split handling" wasn't a problem if the latter was named accumulator() or updater():
The problem is starting a sum with zero is a sumFinder's responsibility. A variable "global" to sumFinder may just not be the way to communicate the running total.

---

regarding TLE:
Imagine a tree with every right null, the root's val 9999 and each left's val "one smaller" stopping at -9999:
How many times does your code visit "node 42"?

---

Imagine an instance method like this:

/** Handles both subtrees recursively, updating <code>maxSum</code> as appropriate.
 * @returns the sum of all node's <code>val</code>s if this subtree is a BST.
 * @…
 */
int sumIfBST(TreeNode root)

How could you handle not a BST? How could you handle not well-formed?

Answer 2

Is there anything I can change, in the same given code, that would optimize it and/or get it accepted?

Your “Time Limit Exceeded” question is basically asking “when is this code slow?” We tend to think of binary trees as “fast”, especially if it’s a balanced binary search tree. Your code does well on such trees.

We also know that sometimes it is “slow”. When is that? Must be when (part of) the input is not a well formed BST.

Now play the role of adversary. You’re dreaming up horrible inputs to feed this code. What should they look like?

First of all, “big”. And also, “unbalanced” / “not well formed”.

Your code’s current goal is to declare “not a BST!” as soon as possible, if indeed it’s not a BST. There are left and right conditions to verify, and either could let us bail early. The current code deterministically investigates the left subtree in its entirety before considering the right. Upon visiting a node it is free to flip a coin and investigate one or the other first.

Let’s maintain a global visits counter. When even, we get the current behavior. When odd, investigate right first, then left.

The idea is that when presented with a giant, highly unbalanced subtree which is not even a BST, we won’t be lured deep into that briar patch.

Now, an adversary who knows or guesses our algorithm may still be able to manipulate it. A source of true random numbers allows to defeat such an adversary. We call this a stochastic algorithm.

---

Actually, a more principled approach would be to track which level we're currently investigating, and explore Left or Right based on the level's low bit.

With only twice as many possible values as there are nodes, the adversary is limited when trying to come up with a valid labeling for some annoyingly unbalanced tree.

---

Let N be number of input nodes, and M <= N is number of nodes that are in well-formed BSTs.

The best we can do is O(M) time complexity, since we must evaluate the inequalities for M nodes. When M is "most" of the nodes, that is, when M is O(N), then the OP code is performant, having O(N) and therefore O(M) complexity.

When M << N, the OP code may fail to complete in O(M) time, as it spends "too long" investigating left subtrees.

Answer 3

Your solution is inefficient; there is no need to run a linear check on each subtree to determine whether or not it is a binary search tree. Instead, you can use a single linear (in the number of nodes) DFS and collect information about each subtree as you go.

In particular, for each subtree, find the minimum and maximum key of any node contained within, the sum of all nodes, and whether it is a BST. These can all be calculated from the information on the subtrees of its two children in constant time. We can use a record to store these values, along with an additional field for the largest sum of keys in a subtree that is a BST that is contained within the current subtree. The final answer can be directly retrieved from this field at the root.

class Solution {
    record SubtreeInfo(int maxBstSum, int sum, int minVal, int maxVal, boolean isBst){}
    public int maxSumBST(TreeNode root) {
        return solve(root).maxBstSum;
    }
    private SubtreeInfo solve(TreeNode node) {
        if (node == null) return new SubtreeInfo(0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE, true);
        SubtreeInfo leftInfo = solve(node.left), rightInfo = solve(node.right);
        int currMaxSum = Math.max(leftInfo.maxBstSum, rightInfo.maxBstSum), 
            currSum = node.val + leftInfo.sum + rightInfo.sum;
        boolean currIsBst = leftInfo.isBst && rightInfo.isBst && leftInfo.maxVal < node.val && rightInfo.minVal > node.val;
        if (currIsBst) currMaxSum = Math.max(currMaxSum, currSum);
        return new SubtreeInfo(currMaxSum, currSum, Math.min(node.val, Math.min(leftInfo.minVal, rightInfo.minVal)),
            Math.max(node.val, Math.max(leftInfo.maxVal, rightInfo.maxVal)), currIsBst);
    }
}