Maximum Sum BST in Binary Tree

Description

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

Primary Approach: Bottom-Up Postorder DFS ($O(N)$ Time, $O(H)$ Space)

Intuition

To determine if a tree rooted at node is a valid BST, we need information from both its left and right subtrees first. A top-down validation approach would re-check nodes repeatedly ($O(N^2)$ time). Using Postorder Traversal ($\text{Left}\to \text{Right}\to \text{Root}$), each node receives 4 essential metrics from its children in a single bottom-up pass:

1. minVal: The minimum value in the subtree.
2. maxVal: The maximum value in the subtree.
3. sum: The sum of all node values in the subtree.
4. isBST: A boolean indicating whether the subtree is a valid BST.

Validation Condition: A node forms a valid BST if and only if:

• Both left and right subtrees are valid BSTs.
• node.val > left.maxVal and node.val < right.minVal.

If valid, update global maxSum = Math.max(maxSum, currSum) and pass updated bounds up to the parent.

class Solution {
    private int maxSum = 0; // Base case: an empty BST has sum = 0
 
    // Helper class to return subtree metadata
    private static class NodeInfo {
        int minVal;
        int maxVal;
        int sum;
        boolean isBST;
 
        NodeInfo(int minVal, int maxVal, int sum, boolean isBST) {
            this.minVal = minVal;
            this.maxVal = maxVal;
            this.sum = sum;
            this.isBST = isBST;
        }
    }
 
    public int maxSumBST(TreeNode root) {
        maxSum = 0;
        postOrder(root);
        return maxSum;
    }
 
    private NodeInfo postOrder(TreeNode node) {
        // Base case: null node is a valid BST with sum 0
        if (node == null) {
            return new NodeInfo(Integer.MAX_VALUE, Integer.MIN_VALUE, 0, true);
        }
 
        // Postorder traversal (Left, Right)
        NodeInfo left = postOrder(node.left);
        NodeInfo right = postOrder(node.right);
 
        // Check if current subtree satisfies BST properties
        if (left.isBST && right.isBST && node.val > left.maxVal && node.val < right.minVal) {
            int currentSum = left.sum + right.sum + node.val;
            maxSum = Math.max(maxSum, currentSum);
 
            int minVal = Math.min(node.val, left.minVal);
            int maxVal = Math.max(node.val, right.maxVal);
 
            return new NodeInfo(minVal, maxVal, currentSum, true);
        }
 
        // If not a valid BST, return isBST = false
        return new NodeInfo(0, 0, 0, false);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every node in the binary tree is visited exactly once in a single bottom-up pass.
• Space Complexity: $O(H)$ — Auxiliary call stack space bounded by the tree height $H$ ($O(\log N)$ for balanced trees, $O(N)$ for skewed trees).

This condition checks whether the subtree rooted at the current node forms a valid Binary Search Tree (BST) by checking four essential requirements:

**1. left.isBST

• Meaning: The left subtree must already be a valid BST.
• Why: If the left subtree contains any BST rule violation internally, the combined tree rooted at node cannot be a valid BST.

**2. right.isBST

• Meaning: The right subtree must already be a valid BST.
• Why: Same logic—if the right subtree is broken internally, the parent tree is also broken.

**3. node.val > left.maxVal

• Meaning: The current node’s value must be strictly greater than the largest value in the left subtree.
• Why: In a BST, every value in the left subtree must be smaller than the root. Checking against left.maxVal guarantees that node.val is greater than every single element on the left side.

**4. node.val < right.minVal

• Meaning: The current node’s value must be strictly smaller than the smallest value in the right subtree.
• Why: In a BST, every value in the right subtree must be larger than the root. Checking against right.minVal guarantees that node.val is smaller than every single element on the right side.

Summary
If all four conditions evaluate to true, the left and right subtrees integrate properly with node, making the whole subtree at node a valid BST.

---

Key Interview Discussion Points

• Why Top-Down fails ($O(N^2)$ vs $O(N)$): A top-down strategy re-calculates BST validity and subtree sums repeatedly for descendant nodes. Postorder DFS solves it in $O(N)$ by bubbling up subtree data in $O(1)$ work per node.
• Base Case Initialization Trick: Returning minVal = Integer.MAX_VALUE and maxVal = Integer.MIN_VALUE for a null leaf simplifies bound checking (node.val > MAX_VALUE fails safely, while node.val > left.maxVal passes for actual leaf nodes).
• Negative Sum Handling: Since an empty BST has a sum of 0, initialize maxSum = 0. If all node values in the tree are negative, the answer defaults to 0 (representing the empty BST subtree).

---

Easy Memory Rule

“Postorder DFS ($\text{Left}\to \text{Right}\to \text{Root}$) returns (min, max, sum, isBST) $\to$ Valid if left.max < node.val < right.min $\to$ Update global maxSum!”