Tap here to switch tabs
Problem
Submissions

Problem: Maximum Sum BST in Binary Tree

Maximum Sum BST in Binary Tree asks you to find the greatest sum of node values among all valid BST subtrees, with an empty subtree contributing zero when values are negative.

Statement

Given the root of a binary tree, find the maximum sum of all keys of any subtree that is also a valid Binary Search Tree (BST).

A valid Binary Search Tree satisfies the following conditions:

  • The left subtree of a node contains only nodes with keys strictly less than the node’s key.

  • The right subtree of a node contains only nodes with keys strictly greater than the node’s key.

  • Both the left and right subtrees must also be valid Binary Search Trees.

Note: An empty subtree is considered a valid Binary Search Tree with a sum of 00.

Constraints:

  • The number of nodes in the tree is in the range [1,4imes104][1, 4 imes 10^4].

  • −4imes104≤-4 imes 10^4 \leq Node.val ≤4imes104\leq 4 imes 10^4

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Sum BST in Binary Tree

Maximum Sum BST in Binary Tree asks you to find the greatest sum of node values among all valid BST subtrees, with an empty subtree contributing zero when values are negative.

Statement

Given the root of a binary tree, find the maximum sum of all keys of any subtree that is also a valid Binary Search Tree (BST).

A valid Binary Search Tree satisfies the following conditions:

  • The left subtree of a node contains only nodes with keys strictly less than the node’s key.

  • The right subtree of a node contains only nodes with keys strictly greater than the node’s key.

  • Both the left and right subtrees must also be valid Binary Search Trees.

Note: An empty subtree is considered a valid Binary Search Tree with a sum of 00.

Constraints:

  • The number of nodes in the tree is in the range [1,4imes104][1, 4 imes 10^4].

  • −4imes104≤-4 imes 10^4 \leq Node.val ≤4imes104\leq 4 imes 10^4