Maximum Sum BST in Binary Tree - Video Solutions

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.