Maximum Sum BST in Binary Tree

HARD

Description

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 1:

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.

Example 2:

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

Example 3:

Input: root = [-4,-2,-5]
Output: 0
Explanation: All values are negatives. Return an empty BST.

Constraints:

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

Approaches

Checkout 2 different approaches to solve Maximum Sum BST in Binary Tree. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Traverse and Validate

This approach iterates through every node of the binary tree. For each node, it treats the subtree rooted at that node as a potential candidate for the maximum sum BST. Two helper functions are used: one to validate if the subtree is a valid BST, and another to calculate the sum of its nodes if it is.

Algorithm

Initialize a variable maxSum = 0.
Traverse the tree using a function, say traverse(node).
For each node in the traversal:
- Call a helper function isBST(node, Long.MIN_VALUE, Long.MAX_VALUE) to check if the subtree at node is a valid BST.
- If it is a BST, call another helper getSum(node) to find its sum.
- Update maxSum = Math.max(maxSum, sum).
Recursively call traverse(node.left) and traverse(node.right).
Return maxSum.

The main idea is to check every possible subtree. We can perform a traversal (e.g., preorder) on the main tree. For each node visited during this traversal, we check if the subtree rooted at this node is a valid BST. To check for a valid BST, we use a recursive helper function, isBST(node, min, max), which verifies the BST property for every node in the subtree. If the subtree is a valid BST, we use another recursive helper, getSum(node), to calculate the sum of all node values in that subtree. We maintain a global variable, maxSum, initialized to 0, and update it whenever we find a valid BST subtree with a sum greater than the current maxSum. This process is repeated for all nodes in the tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxSum = 0;

    public int maxSumBST(TreeNode root) {
        if (root == null) {
            return 0;
        }
        traverse(root);
        return maxSum;
    }

    private void traverse(TreeNode node) {
        if (node == null) {
            return;
        }
        if (isBST(node, Long.MIN_VALUE, Long.MAX_VALUE)) {
            int sum = getSum(node);
            maxSum = Math.max(maxSum, sum);
        }
        traverse(node.left);
        traverse(node.right);
    }

    private boolean isBST(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }
        if (node.val <= min || node.val >= max) {
            return false;
        }
        return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);
    }

    private int getSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + getSum(node.left) + getSum(node.right);
    }
}

Complexity Analysis

Time Complexity: O(N^2) in the worst case (a skewed tree). For each of the N nodes, we might traverse its entire subtree to validate and sum it. In a skewed tree, the sum of subtree sizes is 1 + 2 + ... + N, which is O(N^2).Space Complexity: O(N) in the worst case for the recursion stack depth, where N is the number of nodes.

Pros and Cons

Pros:

Simple to understand and implement.
Directly translates the problem definition into code.

Cons:

Highly inefficient due to redundant computations. The isBST and getSum functions repeatedly traverse the same subtrees for different ancestor nodes.

Code Solutions

Checking out 3 solutions in different languages for Maximum Sum BST in Binary Tree. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Maximum Sum BST in Binary Tree

Algorithms:

Depth-First Search

Patterns:

Dynamic Programming

Data Structures:

TreeBinary TreeBinary Search Tree

Companies:

Zepto |