Is Maximum Sum BST in Binary Tree easy or hard?

The problem is classified as Hard because it requires combining BST validation with dynamic programming on trees. The challenge is designing the correct state to return from each DFS call so parent nodes can determine validity without re-traversing subtrees.

Maximum Sum BST in Binary Tree Python/Java solution

Python and Java implementations both use recursive post-order traversal. The helper function returns a structure containing subtree min, max, sum, and a boolean indicating whether the subtree is a valid BST, while a global variable tracks the maximum sum.

How to solve Maximum Sum BST in Binary Tree in O(n)?

Use post-order depth-first search so each node receives information about its left and right subtrees. Track four values: whether the subtree is a BST, its minimum value, maximum value, and sum. If the BST condition holds (left.max < node.val < right.min), compute the subtree sum and update the global maximum. This processes every node once.

What is the best approach for Maximum Sum BST in Binary Tree?

The best approach is recursive post-order traversal. Each DFS call returns whether the subtree is a valid BST along with its minimum value, maximum value, and sum. By combining results from left and right children, you can validate the BST condition and update the global maximum sum in O(n) time.

Is Maximum Sum BST in Binary Tree asked at Google/Amazon/Meta?

Tree dynamic programming and BST validation problems are commonly asked at companies like Google, Amazon, and Meta. Variations that combine subtree properties, DFS traversal, and constraint propagation appear frequently in senior-level interviews.

What data structure is used in Maximum Sum BST in Binary Tree?

The core data structure is a binary tree. The solution relies on depth-first search with recursion and a small tuple or struct returned from each node containing subtree metadata (min, max, sum, BST validity).

What is the time complexity of Maximum Sum BST in Binary Tree?

The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during post-order DFS. Space complexity is O(h) for the recursion stack, where h is the height of the tree.

Description Hints 2 Solution Video 1:19:24

1373. Maximum Sum BST in Binary Tree

Q: What is the best approach for Maximum Sum BST in Binary Tree?

The best approach is recursive post-order traversal. Each DFS call returns whether the subtree is a valid BST along with its minimum value, maximum value, and sum. By combining results from left and right children, you can validate the BST condition and update the global maximum sum in O(n) time.

Q: Is Maximum Sum BST in Binary Tree asked at Google/Amazon/Meta?

Tree dynamic programming and BST validation problems are commonly asked at companies like Google, Amazon, and Meta. Variations that combine subtree properties, DFS traversal, and constraint propagation appear frequently in senior-level interviews.

Q: What data structure is used in Maximum Sum BST in Binary Tree?

The core data structure is a binary tree. The solution relies on depth-first search with recursion and a small tuple or struct returned from each node containing subtree metadata (min, max, sum, BST validity).

Q: What is the time complexity of Maximum Sum BST in Binary Tree?

The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during post-order DFS. Space complexity is O(h) for the recursion stack, where h is the height of the tree.

Hard48.9% acceptance5 companies

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⁴

Asked at 5 companies

Amazon

Google Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Create a datastructure with 4 parameters: (sum, isBST, maxLeft, minRight).

Hint 2

In each node compute theses parameters, following the conditions of a Binary Search Tree.

1:19:24

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def maxSumBST(self, root: Optional[TreeNode]) -> int:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]

Input

[4,3,null,1,2]

Input

[-4,-2,-5]

Your code is saved on this device.Solution