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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Sum BST in Binary Tree

Difficulty: Hard

Problem 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).

Key Insights

  • A valid BST must have left children less than the node and right children greater than the node.
  • The sum of values in a BST needs to be calculated and compared to find the maximum.
  • A post-order traversal can be used to evaluate sub-trees, checking for BST properties while calculating their sums.
  • We need to maintain the maximum sum found during the traversal of the tree.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we visit each node once. Space Complexity: O(H), where H is the height of the tree due to the recursion stack.

Solution

The solution uses a depth-first search (DFS) approach to traverse the binary tree. For each node, we check if its left and right subtrees are valid BSTs, calculate their sums, and determine if the current subtree can also be considered a BST. If it is valid, we calculate the total sum for this subtree and update the maximum sum if necessary.

The key steps are:

  1. Traverse the tree in a post-order manner.
  2. For each node:
    • Check if its subtrees are BSTs and within valid bounds.
    • Calculate the sum if it's a BST.
    • Update the global maximum sum if the current subtree is a valid BST.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxSumBST(self, root: TreeNode) -> int:
        self.max_sum = 0
        
        def dfs(node):
            if not node:
                return (True, 0, float('inf'), float('-inf'))  # is_bst, sum, min, max
            
            left_is_bst, left_sum, left_min, left_max = dfs(node.left)
            right_is_bst, right_sum, right_min, right_max = dfs(node.right)

            if left_is_bst and right_is_bst and left_max < node.val < right_min:
                total_sum = left_sum + right_sum + node.val
                self.max_sum = max(self.max_sum, total_sum)
                return (True, total_sum, min(left_min, node.val), max(right_max, node.val))
            else:
                return (False, 0, 0, 0)  # Not a BST

        dfs(root)
        return self.max_sum
← Back to All Questions