Maximum Sum BST in Binary Tree

HardTreestree dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a binary tree, find the subtree that is a valid **binary search tree** and has the largest sum of node values. Return that sum. A subtree means a node together with all of its descendants. It is a valid BST when, for every node in it, all values in its left subtree are **strictly smaller** and all values in its right subtree are **strictly larger** than the node's value. The empty tree counts as a BST with sum 0, so the answer is never negative. Aim for a single O(n) traversal.

Examples

Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
The subtree rooted at 3 (values 2, 3, 4, 5, 6) is a BST with sum 20.
Input: root = [4,3,null,1,2]
Output: 2
The best BST is the single leaf 2.
Input: root = [-4,-2,-5]
Output: 0
Every non-empty BST has a negative sum, so the empty tree wins.

Constraints

  • 1 <= number of nodes <= 4 * 10^4
  • -4 * 10^4 <= Node.val <= 4 * 10^4

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More tree dp problems