We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Sum BST in Binary Tree

Number: 1475

Difficulty: Hard

Paid? No

Companies: Amazon, Bloomberg, Meta

Problem Description

Given a binary tree, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST). 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.

Key Insights

  • Use a post-order traversal to gather information (validity, sum, min, and max) for each subtree.
  • For each node, determine if its subtree is a BST by comparing node values against the maximum of the left subtree and the minimum of the right subtree.
  • Maintain a global variable to track the highest BST sum encountered during traversal.
  • Return an empty BST (sum = 0) if all valid BSTs result in a negative sum.

Space and Time Complexity

Time Complexity: O(n), as each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to recursive call stack.

Solution

We perform a post-order traversal of the tree. For each node, we recursively inspect its left and right subtrees. Each recursive call returns a tuple (or equivalent structure) containing:

  • A boolean indicating whether the subtree is a BST.
  • The sum of all node values in the subtree.
  • The minimum value in the subtree.
  • The maximum value in the subtree.

A node's subtree is a BST if:

  • Both left and right subtrees are BSTs.
  • The node's value is greater than the maximum value in the left subtree.
  • The node's value is less than the minimum value in the right subtree.

If valid, update the global maximum sum with the current BST subtree sum. Otherwise, mark the subtree as invalid. This approach leverages recursion and dynamic programming principles to efficiently evaluate each subtree.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxSumBST(self, root: TreeNode) -> int:
        self.max_sum = 0
        
        def traverse(node):
            if not node:
                # An empty tree is a BST, with a sum of 0
                # and extreme min/max values for easy comparisons.
                return (True, 0, float('inf'), float('-inf'))
            
            left_is_bst, left_sum, left_min, left_max = traverse(node.left)
            right_is_bst, right_sum, right_min, right_max = traverse(node.right)
            
            if left_is_bst and right_is_bst and node.val > left_max and node.val < right_min:
                current_sum = node.val + left_sum + right_sum
                self.max_sum = max(self.max_sum, current_sum)
                current_min = min(left_min, node.val)
                current_max = max(right_max, node.val)
                return (True, current_sum, current_min, current_max)
            else:
                return (False, 0, 0, 0)
        
        traverse(root)
        return self.max_sum
← Back to All Questions