Skip to main content
Talentd

Maximum Sum BST in Binary Tree - Solution & Explanation

HardDynamic ProgrammingTreeDepth-First SearchBinary Search Tree21 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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 * 104].
  • -4 * 104 <= Node.val <= 4 * 104

Approach Overview

Problem Overview: You are given a binary tree that is not necessarily a binary search tree. The goal is to find the maximum sum of values among all subtrees that satisfy the binary search tree property. Any node can be the root of such a subtree, and the subtree must obey BST ordering rules: left values smaller than the node and right values greater.

Approach 1: Brute Force Subtree Validation (O(n^2) time, O(h) space)

Check every node as a potential root of a BST subtree. For each node, perform a validation pass to verify whether the subtree satisfies BST constraints using min/max bounds, then compute the sum of its nodes. This requires traversing the same nodes multiple times. In the worst case (skewed trees), every node triggers a full subtree scan, giving O(n^2) time complexity. Space complexity is O(h) due to recursion depth where h is the tree height.

This approach is straightforward but inefficient. It helps you reason about the problem: each subtree must be validated independently and its sum calculated. The repeated traversal becomes the bottleneck.

Approach 2: Recursive Post-order Traversal (O(n) time, O(h) space)

The optimal solution processes the tree using depth-first search in post-order. Each recursive call returns four pieces of information about the current subtree: whether it is a valid BST, the minimum value inside it, the maximum value inside it, and the sum of all nodes.

Post-order traversal ensures left and right subtrees are evaluated before the parent node. When visiting a node, you combine results from its children. The subtree is a valid BST if:

left.isBST && right.isBST && left.max < node.val < right.min

If the condition holds, compute the new sum as left.sum + right.sum + node.val, update the global maximum, and propagate updated min/max boundaries upward. If the condition fails, mark the subtree as invalid so parent nodes cannot treat it as a BST.

This technique resembles bottom-up dynamic programming on a binary tree. Each node contributes a small state summary that allows its parent to determine BST validity without re-traversing nodes. Every node is processed exactly once, producing O(n) time complexity with O(h) recursion stack space.

Recommended for interviews: Interviewers expect the post-order DFS solution. The brute force approach shows you understand BST validation but does not scale. The recursive post-order method demonstrates tree DP thinking: aggregate subtree properties, propagate constraints upward, and compute the answer in a single traversal.

Approach 1: Recursive Post-order Traversal

In this approach, we perform a post-order traversal of the tree. For each node, we compute whether its left and right subtrees form BSTs, and if they do, their sum. The maximum BST sum is updated whenever a valid BST subtree is found.

We use a helper function that returns four values: whether the subtree is a BST, the sum of all nodes in this subtree, the minimum value in this subtree, and the maximum value in this subtree.

The code defines a helper function postOrder that concurrently checks for a BST and calculates its sum. This function is called recursively for left and right subtrees, updating the maximum sum as it finds BSTs.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as each node is visited exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

Try this approach in the editor →

Approach 2: DFS

To determine whether a tree is a binary search tree, it needs to meet the following four conditions:

  • The left subtree is a binary search tree;
  • The right subtree is a binary search tree;
  • The maximum value of the left subtree is less than the value of the root node;
  • The minimum value of the right subtree is greater than the value of the root node.

Therefore, we design a function dfs(root), the return value of the function is a quadruple (bst, mi, mx, s), where:

  • The number bst indicates whether the tree with root as the root is a binary search tree. If it is a binary search tree, then bst = 1; otherwise bst = 0;
  • The number mi represents the minimum value of the tree with root as the root;
  • The number mx represents the maximum value of the tree with root as the root;
  • The number s represents the sum of all nodes of the tree with root as the root.

The execution logic of the function dfs(root) is as follows:

If root is an empty node, return (1, +infty, -infty, 0), indicating that the empty tree is a binary search tree, the minimum value and maximum value are positive infinity and negative infinity respectively, and the sum of nodes is 0.

Otherwise, recursively calculate the left subtree and right subtree of root, and get (lbst, lmi, lmx, ls) and (rbst, rmi, rmx, rs) respectively, then judge whether the root node meets the conditions of the binary search tree.

If lbst = 1 and rbst = 1 and lmx < root.val < rmi, then the tree with root as the root is a binary search tree, and the sum of nodes s= ls + rs + root.val. We update the answer ans = max(ans, s), and return (1, min(lmi, root.val), max(rmx, root.val), s).

Otherwise, the tree with root as the root is not a binary search tree, we return (0, 0, 0, 0).

We call dfs(root) in the main function. After execution, the answer is ans.

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Post-order Traversal

Time Complexity: O(n), as each node is visited exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subtree ValidationO(n^2)O(h)Conceptual starting point when learning BST validation or reasoning about subtree checks
Recursive Post-order Traversal (Tree DP)O(n)O(h)Optimal approach for interviews and production; processes each node once

Video Solution

Largest Binary Search Tree | Maximum Sum BST in Binary Tree | Leetcode • Coder Army • 20,091 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Maximum Sum BST in Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Regular Expression Matching