Maximum Sum BST in Binary Tree

Hard

#1273Time: 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: O(N) in the worst case for the recursion stack depth, where N is the number of nodes.1 company

Patterns

Dynamic Programming

Algorithms

Depth-First Search

Data structures

Tree Binary Tree Binary Search Tree

Companies

Zepto

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int maxSum = 0;18 19    public int maxSumBST(TreeNode root) {20        if (root == null) {21            return 0;22        }23        traverse(root);24        return maxSum;25    }26 27    private void traverse(TreeNode node) {28        if (node == null) {29            return;30        }31        if (isBST(node, Long.MIN_VALUE, Long.MAX_VALUE)) {32            int sum = getSum(node);33            maxSum = Math.max(maxSum, sum);34        }35        traverse(node.left);36        traverse(node.right);37    }38 39    private boolean isBST(TreeNode node, long min, long max) {40        if (node == null) {41            return true;42        }43        if (node.val <= min || node.val >= max) {44            return false;45        }46        return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);47    }48 49    private int getSum(TreeNode node) {50        if (node == null) {51            return 0;52        }53        return node.val + getSum(node.left) + getSum(node.right);54    }55}

Complexity

Time

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

O(N) in the worst case for the recursion stack depth, where N is the number of nodes.

Trade-offs

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.

Solutions

Solution

1/** * 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 { private int ans ; private final int inf = 1 << 30 ; public int maxSumBST ( TreeNode root ) { dfs ( root ); return ans ; } private int [] dfs ( TreeNode root ) { if ( root == null ) { return new int [] { 1 , inf , - inf , 0 }; } var l = dfs ( root . left ); var r = dfs ( root . right ); int v = root . val ; if ( l [ 0 ] == 1 && r [ 0 ] == 1 && l [ 2 ] < v && r [ 1 ] > v ) { int s = v + l [ 3 ] + r [ 3 ]; ans = Math . max ( ans , s ); return new int [] { 1 , Math . min ( l [ 1 ], v ), Math . max ( r [ 2 ], v ), s }; } return new int [ 4 ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem