FastPrepMaximum Sum BST in a Binary Tree
Problems/Maximum Sum BST in a Binary Tree

Maximum Sum BST in a Binary Tree

Amazon logoAmazon● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Amazon SDE2 interview list as Maximum Sum BST in Binary Tree. Problem match confidence: approximately 99%.

Given the root of a binary tree, find the maximum sum of node values among all subtrees that are valid binary search trees.

A valid BST has every left-subtree value strictly smaller than its root and every right-subtree value strictly larger. Return 0 when every valid non-empty BST subtree has a negative sum.

Function

maxSumBST(root: TreeNode) → int

Examples

Example 1

root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]return = 20

The subtree rooted at 3 is a BST with sum 20.

Example 2

root = [4,3,null,1,2]return = 2

The leaf with value 2 is the best valid BST subtree.

Example 3

root = [-4,-2,-5]return = 0

All valid BST sums are negative, so zero is returned.

Constraints

  • The tree contains between 0 and 5000 nodes.
  • -10000 ≤ Node.val ≤ 10000.

More Amazon problems

  • Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
  • First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
See Amazon hiring insights
Saved
/**
 * 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 {
    public int maxSumBST(TreeNode root) {
        // write your code here
    }
}
Checking account…