DSA sheet · Trees · Binary Search Tree pattern

Maximum Sum BST in Binary Tree

This video joins two things we already know: checking whether a tree is a BST (the min/max idea from Validate BST) and adding up a subtree (the sum idea from Maximum Path Sum style problems). The tree we get is a normal binary tree, not a BST. Somewhere inside it there are smaller pieces that are BSTs, and we want the piece with the biggest total.

The real lesson is deciding what each node must send up to its parent. The teacher says that once you know what to return for an empty node, half the code is already written. We'll spend most of this page on that question.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

Part 0 · What you must know before starting
Part A · Max Sum BST with bottom-up DFS (return 4 things)
Part B · Revision page

Part 0 · Before starting

What is a tree node?

Each node is a small box holding a value, a link to its left child and a link to its right child. A missing child is None.

given by LeetCode, don't write this in the solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Words we will use

Subtree of a node: that node plus everything hanging below it. Every node is the top (root) of its own subtree.
Leaf: a node with no children.
Key: just another word for the value stored in a node.

The BST property (read this carefully)

A Binary Search Tree (BST) is a binary tree where, for every node:

every value in its left subtree is smaller than the node, and
every value in its right subtree is bigger than the node.

"Every value in the subtree" means all nodes below, not just the direct children. Checking only the children is a classic mistake:

BST ✓

NOT a BST ✗

In the second tree, 6 is a fine right child of 3 (6 > 3). But 6 sits inside the left subtree of 5, so it must be smaller than 5. It isn't, so the whole tree is not a BST.

The neat way to check this: compare with the max of the left side and the min of the right side

"All left values are smaller than me" is the same as saying "the biggest left value is smaller than me". In the same way, "all right values are bigger than me" is the same as "the smallest right value is bigger than me". So a node is the root of a BST when:

BST check at one node left subtree is a BST · right subtree is a BST · max(left) < node.val < min(right)

This is the key fact the whole solution uses.

Two small facts we will need

Every leaf is a BST. It has nothing on the left or right, so there's nothing that could break the rule.
An empty tree (None) is also a BST. To break the BST rule you need some node in the wrong place. An empty tree has no nodes, so nothing is broken.

(You might know that an inorder walk of a BST gives sorted values. This problem doesn't need that fact. We use the min/max check instead, because we need the answer for every subtree in one pass.)

Bottom-up DFS (postorder)

Postorder means: first finish the left child, then the right child, and only then handle the node itself. So a node makes its decision after both children have reported back. Information travels from the leaves up to the root. That's exactly what we need here.

Part A · Max Sum BST with bottom-up DFS

LeetCode 1373

1The question in simple words

You get the root of a binary tree (not necessarily a BST). Look at every subtree. Some of them are BSTs, some aren't. Among the subtrees that are BSTs, add up all their values. Return the largest such sum.

One special rule (Example 3 on LeetCode): if every BST sum is negative, return 0. You can think of it as "an empty subtree is also a BST, and its sum is 0".

Example 1 → answer 20

Example 2 → answer 2

Example 3 → answer 0

       -4
       /  \
     -2    -5

The teacher goes through Example 1 piece by piece:

subtree rooted at	is it a BST?	sum
left 2 (leaf)	yes, every leaf is	2
left 4's right child 4 (leaf)	yes	4
left 4 (with children 2 and 4)	no: its right child 4 is equal, not bigger	not counted
5 (with children 4 and 6)	yes: 4 < 5 < 6	4 + 5 + 6 = 15
3 (with 2 on the left, 5-4-6 on the right)	yes: 2 < 3 < everything on the right	2 + 3 + 15 = 20
1 (the whole tree)	no: its left subtree is already not a BST	not counted

The biggest sum among the BSTs is 20.

In the video the teacher first says 16 for the 4-5-6 subtree, then corrects herself to 15. 15 is right.

Example 2: the leaves 1 and 2 are BSTs. Node 3 has 2 on its right, which is smaller than 3, so 3's subtree is not a BST, and so 4's isn't either. The best is the single leaf 2.

Example 3: the leaves −2 and −5 are BSTs, but their sums are negative. Node −4 isn't a BST (−2 on its left is bigger than −4). Every real BST sum is negative, so the answer is 0.

2What the constraints tell us

Number of nodes: 1 to 4·10⁴. An O(n²) idea would cost (4·10⁴)² = 16·10⁸ = 1.6·10⁹ steps. That's above the ~10⁸ we can afford, so it would get TLE (Time Limit Exceeded). We need O(n) (or close to it).
Values: −4·10⁴ to 4·10⁴. Since we're adding values, the teacher asks: how big can a sum get? The worst case is that every node holds 4·10⁴ and the whole tree is one BST. Then the sum is 4·10⁴ × 4·10⁴ = 1.6·10⁹.
That's close to the limit of a normal 32-bit int (about 2.1·10⁹) in Java or C++. The teacher's thinking: in such a case you'd normally switch to long to be safe. She tries int first because negative values make the real sums smaller, and keeps long as the fallback if a test fails. In Python this doesn't matter, because Python ints never overflow.
Values can be negative. That's why we start the "smallest so far" at +∞ and "biggest so far" at −∞. Any real value, even −4·10⁴, will beat those starting values.

3Intuition: a report card from each child

Picture each node as a team leader. Before deciding anything, the leader asks both children to hand in a short report about their subtree. Using only the two reports and its own value, the leader can tell:

whether its own subtree is a BST,
and if it is, its sum. That sum is a candidate for the answer.

Then the leader writes its own report and hands it up to its parent. Nobody ever has to walk back down into a subtree. That's what makes it fast.

The whole problem comes down to: what must be written on the report card?

4Building the logic from examples

Step 4a: should we start at the root (top-down) or at the leaves (bottom-up)?

Stand at the root 1 in Example 1. Can you say whether the whole tree is a BST? No. You'd have to know what's going on in all the levels below first. The same is true at every node: the answer depends on what's underneath.

So deciding at the top doesn't make sense. We still enter from the root (it's the only node we're given), but we don't decide anything there. We first travel down to the bottom, and the decisions are made on the way back up, after both children have answered. That's postorder.

Doubt: what's wrong with the simple way, "for every node, run a full Validate BST on its subtree, and if it passes, add up the subtree"?
→ It gives the right answer, but each node starts a fresh walk over its whole subtree. For a long chain-shaped tree that's 1 + 2 + … + n ≈ n²/2 steps. With n = 4·10⁴ that's about 10⁹, which is TLE (see step 2). The bottom-up way reuses what the children already worked out, so each node is visited only once.

Step 4b: what does a node need from its children?

Take node 3 in Example 1 (left child 2, right subtree 5-4-6). To decide "is my subtree a BST?", it needs:

Is my left subtree a BST? Is my right subtree a BST? If either one isn't, I can't be one either. (That's why the root 1 fails: its left side, rooted at 4, already failed.)
The biggest value on my left, to check left max < 3.
The smallest value on my right, to check 3 < right min.
The sum of my left subtree and the sum of my right subtree, so I can get my own sum as left sum + right sum + 3 without walking through the subtree again.

Doubt 1: the parent only needs the max from its left child and the min from its right child. Why does every node return both min and max?
→ A node doesn't know whether it's a left child or a right child of its parent. If it's a left child, the parent will read its max. If it's a right child, the parent will read its min. The simplest fix, as the teacher says, is to always return both and let the parent pick what it needs.

Doubt 2: why carry the sum up? Can't the node just add up its subtree when it needs to?
→ That would mean walking the whole subtree again, an extra O(n) at each node, so O(n²) overall. The children have already worked out their own sums on the way up, so the node just adds two numbers and its own value in O(1).

The report card: 4 things, always in this order [0] is it a BST? (True/False, or 1/0) · [1] smallest value in the subtree · [2] biggest value in the subtree · [3] sum of the subtree

The teacher uses an int array of size 4, with 1/0 for yes/no, and says True/False works just as well. In Python we return a tuple and unpack it into named variables, which is easier to read.

Step 4c: the base case. What does an empty spot (None) report?

This is the line the teacher says is half the battle. Go down to the leaf 2 in Example 1. Its left and right are None. What should None say so that the leaf 2 ends up correctly marked as a BST with min 2, max 2, sum 2?

Is it a BST? → True. An empty tree breaks no rule. If we said False, every leaf would be marked "not a BST" (because a node needs both children to be BSTs), then every parent of a leaf would fail too, and nothing would ever count.
Its max → −∞. The parent checks left max < parent.val. With nothing on the left, this check must always pass. −∞ is smaller than any number, so it does.
Its min → +∞. The parent checks parent.val < right min. With nothing on the right, this must always pass. +∞ is bigger than any number.
Its sum → 0. Nothing there, nothing to add.

Base caseif root is None: return (True, +∞, −∞, 0)
That is: is BST, min = +∞, max = −∞, sum = 0.

Doubt: isn't it strange that min = +∞ is bigger than max = −∞?
→ It looks odd, but it's on purpose. These are "neutral" starting values: any real value will replace them as soon as it shows up. When the leaf 2 computes its own min as min(left min, 2) = min(+∞, 2) = 2, the +∞ disappears. Same for max. The constraints allow values down to −4·10⁴, so a smaller starting value like 0 would be wrong. It has to be ±∞.

Step 4d: checking a node, using the leaf 2

The leaf 2 gets (True, +∞, −∞, 0) from both sides. Check:

left is a BST ✓, right is a BST ✓
left max (−∞) < 2 ✓ and 2 < right min (+∞) ✓ → so 2 sits between −∞ and +∞

So the leaf is a BST. Its sum = 0 + 0 + 2 = 2. Update the best answer: max_sum = max(max_sum, 2) = 2.

Step 4e: what the leaf hands up: the new min and max

Leaf 2 now has to fill its own report for its parent (the left 4). Is BST = True, sum = 2. What are its min and max?

New min = min(left min, my value) = min(+∞, 2) = 2
New max = max(right max, my value) = max(−∞, 2) = 2

So it reports (True, 2, 2, 2). The other leaf 4 reports (True, 4, 4, 4).

Doubt: why compare the min only with the left min, and the max only with the right max? Shouldn't the min be the smallest of left, right and me?
→ We only reach this line when the subtree is a BST. In a BST, the smallest value is always on the left side (everything there is smaller than the node), and the biggest is always on the right. Take subtree 3 in Example 1: its smallest value (2) is on the left and its biggest (6) is on the right. The right side can't hold anything smaller than the node, and the left side can't hold anything bigger. So checking left min against the node, and right max against the node, is enough. Each is one O(1) comparison, because the child has already worked out the min/max of its whole subtree. We never re-scan it.

Step 4f: a node that fails, the left 4 in Example 1

The left 4 receives (True, 2, 2, 2) from its left and (True, 4, 4, 4) from its right.

both children are BSTs ✓
left max 2 < 4 ✓
4 < right min 4? No, 4 = 4. In a BST the right side must be strictly bigger, so equal fails.

So this subtree is not a BST. What should it report?

Is BST = False (0). This is the only part that really matters.
Sum = 0. We must not add it to anything, and adding 0 means adding nothing.
Min = 0, max = 0. Any values would do. Once the flag says "not a BST", the parent's check stops at the very first condition and never reads the min or max. So the teacher just puts 0, 0.

Not-a-BST reportreturn (False, 0, 0, 0)
min/max are never read, because the parent's check fails at the flag first.

Doubt: once a subtree fails, can any node above it still be a BST?
→ No. A BST needs both of its subtrees to be BSTs. So a failure travels all the way up that path. That's why root 1 fails at once: its left report says False. It doesn't matter that the right side, 3, is a great BST. But the answer is safe, because we updated max_sum to 20 the moment 3 was checked. The final return value from the root is never used. Only the global max_sum matters.

Step 4g: the starting value of the answer, and Example 3

In the editor the teacher first starts the answer at the smallest integer (−∞), since values can be negative. Then she notices Example 3: if every BST sum is negative, the expected output is 0, not a negative number. Starting at −∞ would return −2 for Example 3 (the leaf −2), which is wrong. So the answer must start at 0.

Doubt (fix in these notes): why 0 and not −∞?
→ An empty subtree counts as a BST with sum 0, so 0 is always a possible answer. Starting max_sum = 0 means any negative BST sum never beats it. That's exactly what Example 3 wants. The code below uses 0.

5Approach steps

Keep a global max_sum = 0.
Write solve(node) that returns (is_bst, min, max, sum) for that subtree.
If the node is None → return (True, +∞, −∞, 0).
Otherwise first get the left report and the right report (go to the bottom first).
If both are BSTs and left max < node.val < right min → this subtree is a BST: sum = left sum + right sum + node.val; update max_sum; min = min(left min, node.val); max = max(right max, node.val); return (True, min, max, sum).
Else → return (False, 0, 0, 0).
Call solve(root), ignore what it returns, and return max_sum.

6Code (Python)

Max Sum BST, bottom-up DFS

import sys
sys.setrecursionlimit(100000)   # a chain-shaped tree can be 4*10^4 deep

class Solution:
    def maxSumBST(self, root):
        self.max_sum = 0          # 0, not -infinity (Example 3)
        self.solve(root)
        return self.max_sum

    def solve(self, root):
        # returns (is_bst, smallest, biggest, total)
        if root is None:
            return (True, float('inf'), float('-inf'), 0)

        l_bst, l_min, l_max, l_sum = self.solve(root.left)
        r_bst, r_min, r_max, r_sum = self.solve(root.right)

        if l_bst and r_bst and l_max < root.val < r_min:
            total = l_sum + r_sum + root.val
            self.max_sum = max(self.max_sum, total)
            smallest = min(l_min, root.val)
            biggest = max(r_max, root.val)
            return (True, smallest, biggest, total)

        return (False, 0, 0, 0)    # min/max never read when not a BST

The teacher's array indexes map to our names like this: left[0] = l_bst, left[1] = l_min, left[2] = l_max, left[3] = l_sum (and the same for right). Her check left[2] < root.val < right[1] is our l_max < root.val < r_min.

Doubt: why the setrecursionlimit line?
→ Python allows only about 1000 nested calls by default. A tree of 4·10⁴ nodes shaped like a straight line makes 4·10⁴ nested calls, which would crash. Java and C++ don't hit this limit as early, so the teacher doesn't mention it. It's a Python-only safety line.

7Code line by line

line	what it means
self.max_sum = 0	The best BST sum seen so far. It starts at 0 because an empty BST (sum 0) is always allowed, and that's what makes Example 3 return 0.
self.solve(root) return self.max_sum	Run the DFS just for its side effect of updating `max_sum`. The root's own report isn't needed.
if root is None: return (True, inf, -inf, 0)	Empty spot: it's a BST, min = +∞ and max = −∞ so the parent's comparisons always pass, sum = 0. Also the base case that stops the recursion.
... = self.solve(root.left) ... = self.solve(root.right)	Go all the way down first (postorder). We can't decide anything at this node until both reports are in.
if l_bst and r_bst	Both sides must be BSTs. If the first one is False, Python doesn't even look at the rest, so the dummy 0, 0 min/max of a failed child are never compared.
l_max < root.val < r_min	The node is bigger than everything on its left (the biggest left value is enough) and smaller than everything on its right (the smallest right value is enough). Strict `<`, so equal values fail.
total = l_sum + r_sum + root.val	The whole subtree's sum in O(1), using the sums the children already worked out.
self.max_sum = max(...)	This subtree is a BST, so its sum is a candidate. Keep the bigger one.
smallest = min(l_min, root.val)	In a BST the smallest value is on the left side, or the node itself if the left is empty (then l_min is +∞).
biggest = max(r_max, root.val)	The biggest value is on the right side, or the node itself if the right is empty (then r_max is −∞).
return (True, smallest, biggest, total)	The report card for the parent.
return (False, 0, 0, 0)	Not a BST: tell the parent "don't use me". The sum is 0, and min/max are dummies.

8Dry run on Example 1

          1
        /   \
      4a     3
      / \   / \
     2   4b 2'  5
              / \
             4'  6          (4a, 4b, 2', 4' just label repeated values)

Report = (is BST, min, max, sum). N = None, which always reports (T, +∞, −∞, 0). best = max_sum.

solve(1) → go left first. 1 waits on the stack.
solve(4a) → go left. 4a waits.
solve(2) → left N, right N, both (T, +∞, −∞, 0). Check −∞ < 2 < +∞ ✓ → sum 2, best = 2, min = min(+∞, 2) = 2, max = max(−∞, 2) = 2 → returns (T, 2, 2, 2).
solve(4b) → same as a leaf → sum 4, best = 4 → returns (T, 4, 4, 4).
Back in 4a: both BSTs ✓, left max 2 < 4 ✓, but 4 < right min 4? no → returns (F, 0, 0, 0).
Back in 1, now go right: solve(3) → go left: solve(2') → leaf → (T, 2, 2, 2), best stays 4.
3 goes right: solve(5) → solve(4') → (T, 4, 4, 4); solve(6) → (T, 6, 6, 6), best = 6.
Back in 5: both BSTs ✓, 4 < 5 < 6 ✓ → sum = 4 + 6 + 5 = 15, best = 15, min = min(4, 5) = 4, max = max(6, 5) = 6 → (T, 4, 6, 15).
Back in 3: left (T, 2, 2, 2), right (T, 4, 6, 15). Both BSTs ✓, 2 < 3 ✓, 3 < 4 ✓ → sum = 2 + 15 + 3 = 20, best = 20, min = 2, max = 6 → (T, 2, 6, 20).
Back in 1: left report is (F, 0, 0, 0) → the check fails at the first condition → returns (F, 0, 0, 0). This return value isn't used by anyone.
maxSumBST returns max_sum = 20 ✓

step 3 (deepest on the left)

solve(1)solve(4a)solve(2)solve(N) → (T,+∞,−∞,0)

step 5

solve(1)solve(4a) → (F,0,0,0)

step 8

solve(1)solve(3)solve(5) → (T,4,6,15)

Top of the stack is the newest call. Each call leaves the stack as soon as it returns its report to the call below it.

Quick check on Example 2 and Example 3

Example 2 (4 → 3 → children 1, 2): leaf 1 → (T,1,1,1), best 1. Leaf 2 → (T,2,2,2), best 2. Node 3: left max 1 < 3 ✓, but 3 < right min 2? no → (F,0,0,0). Node 4: left is F → F. Answer 2 ✓
Example 3 (−4 with −2, −5): leaf −2 → sum −2, max(0, −2) = 0, best stays 0. Leaf −5 → best stays 0. Node −4: left max −2 < −4? no → F. Answer 0 ✓ (with a −∞ start it would wrongly be −2).

9Complexity & remember

Time O(n): every node is visited exactly once, and at each node we do only a few comparisons and additions (O(1)). We never go back down into a subtree, because the children's reports carry everything we need.
Space O(h), where h is the height of the tree: that's how many calls wait on the stack at once. For a balanced tree h ≈ log n. For a skewed (chain-shaped) tree h = n, so the worst case is O(n).

Remember Max Sum BST Go bottom-up. Every node returns (is BST, min, max, sum).
None → (True, +∞, −∞, 0). Not a BST → (False, 0, 0, 0).
BST if both kids are BSTs and left max < val < right min. Then update the answer, min = min(left min, val), max = max(right max, val).
The answer starts at 0.

Part B · Revision page

What each node returns, and why

slot	value for None	value for a BST node	value for a non-BST node	why the parent needs it
[0] is BST	True	True	False	a node can be a BST only if both kids are
[1] min	+∞	min(left min, val)	0 (unused)	if this subtree is a right child, the parent checks `parent < min`
[2] max	−∞	max(right max, val)	0 (unused)	if this subtree is a left child, the parent checks `max < parent`
[3] sum	0	left sum + right sum + val	0	lets the parent get its own sum in O(1)

idea	time	verdict for n = 4·10⁴
validate and sum each subtree separately (top-down)	O(n²)	≈10⁹, TLE
bottom-up DFS returning 4 things	O(n)	passes

If you remember only 5 lines 1. You can't decide at the top, so go to the leaves and decide on the way up (postorder).
2. Each node returns 4 things: is BST, min, max, sum.
3. Empty node: True, +∞, −∞, 0, so any leaf passes the check.
4. BST check: both kids BST and left max < val < right min. Then update the global answer.
5. Not BST: return False, 0, 0, 0. The answer starts at 0, not −∞.

Mistakes to avoid ✗ returning False for None (then no leaf is ever a BST)
✗ starting min at 0 or max at 0 for None (values can be negative, so use ±∞)
✗ comparing with the left/right child instead of the left max/right min of the whole subtree
✗ using <=: equal values are not allowed (the 4-under-4 case)
✗ starting the answer at −∞ (Example 3 expects 0)
✗ re-summing the subtree at each node (turns O(n) into O(n²))

test it yourself (paste under the solution above)

ex1 = TreeNode(1,
        TreeNode(4, TreeNode(2), TreeNode(4)),
        TreeNode(3, TreeNode(2), TreeNode(5, TreeNode(4), TreeNode(6))))
ex2 = TreeNode(4, TreeNode(3, TreeNode(1), TreeNode(2)))
ex3 = TreeNode(-4, TreeNode(-2), TreeNode(-5))

s = Solution()
print(s.maxSumBST(ex1))   # 20
print(s.maxSumBST(ex2))   # 2
print(s.maxSumBST(ex3))   # 0

Based on this video: Maximum Sum BST in Binary Tree