Introduction

In this blog post, we will explore how to solve the LeetCode problem "1373" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 104]. -4 104 <= Node.val <= 4 * 104

Explanation

Here's a breakdown of the solution:

• Bottom-Up Traversal: The solution uses a post-order (bottom-up) traversal of the binary tree. This ensures that when we process a node, we've already processed its left and right subtrees. This is crucial for determining if a subtree rooted at the current node is a BST.
• BST Validation and Sum Calculation: For each node, we check if its left and right subtrees are BSTs and if the current node's value adheres to the BST property (greater than all values in the left subtree, smaller than all values in the right subtree). If it is a valid BST, we calculate the sum of the subtree.

• Maximum Sum Tracking: We maintain a global variable max_sum to keep track of the maximum BST sum encountered so far during the traversal.

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.

• Space Complexity: O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H = N. In the best case (balanced tree), H = logN.

Code

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

class Solution:
    def __init__(self):
        self.max_sum = 0

    def max_bst_sum(self, root: TreeNode) -> int:
        self.max_sum = 0
        self.bst_helper(root)
        return self.max_sum

    def bst_helper(self, node: TreeNode) -> tuple:
        """
        Recursive helper function to check if a subtree is a BST and calculate its sum.

        Returns:
        - is_bst: True if the subtree rooted at 'node' is a BST, False otherwise.
        - min_val: The minimum value in the subtree.
        - max_val: The maximum value in the subtree.
        - sum_val: The sum of all node values in the subtree.
        """
        if not node:
            return True, float('inf'), float('-inf'), 0

        left_bst, left_min, left_max, left_sum = self.bst_helper(node.left)
        right_bst, right_min, right_max, right_sum = self.bst_helper(node.right)

        if (left_bst and right_bst and
            node.val > left_max and node.val < right_min):

            current_sum = left_sum + right_sum + node.val
            self.max_sum = max(self.max_sum, current_sum)

            return True, min(left_min, node.val), max(right_max, node.val), current_sum
        else:
            return False, float('-inf'), float('inf'), 0