Sum BSTs

Tags

Sum BSTs

Category

Binary Search Trees

Difficulty

Hard

Problem Statement

Given a binary tree (not necessarily a BST), find the sum of all node values across all subtrees that are valid Binary Search Trees. A subtree rooted at a node is a valid BST if every node in it satisfies the BST property. Single nodes are considered valid BSTs. Return the total sum of node values from all such valid BST subtrees.

Intuition

We need to check every subtree for the BST property and sum the values of those that qualify. A subtree rooted at a node is a valid BST if: (1) the left subtree is a valid BST, (2) the right subtree is a valid BST, (3) the node's value is greater than the maximum in the left subtree, and (4) the node's value is less than or equal to the minimum in the right subtree. By passing min, max, sum, and validity information up from children to parents in a post-order traversal, we can determine this efficiently.

Approach

  1. Define a recursive function that returns, for each subtree: whether it is a valid BST, the minimum value, the maximum value, and the sum of its nodes.
  2. Base case: a null node returns (isBST=true, min=+infinity, max=-infinity, sum=0).
  3. Recursively compute the info for the left and right subtrees.
  4. The current subtree is a valid BST if:
    • Left subtree is a valid BST
    • Right subtree is a valid BST
    • node.value > leftMax
    • node.value <= rightMin
  5. If valid, compute currentSum = leftSum + rightSum + node.value and add it to a running total.
  6. Return the appropriate min, max, and sum for the current subtree.

Pseudocode

function sumBsts(root):
    totalSum = 0
    getSubtreeInfo(root, totalSum)
    return totalSum

function getSubtreeInfo(node, totalSum):
    if node is null:
        return { isBst: true, min: +infinity, max: -infinity, sum: 0 }

    leftInfo = getSubtreeInfo(node.left, totalSum)
    rightInfo = getSubtreeInfo(node.right, totalSum)

    isBst = leftInfo.isBst and rightInfo.isBst
             and node.value > leftInfo.max
             and node.value <= rightInfo.min

    currentMin = min(node.value, leftInfo.min)
    currentMax = max(node.value, rightInfo.max)
    currentSum = leftInfo.sum + rightInfo.sum + node.value

    if isBst:
        totalSum += currentSum

    return { isBst: isBst, min: currentMin, max: currentMax, sum: currentSum }

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Each node is visited exactly once in the post-order traversal.
  • Space: O(h) where h is the height of the tree, due to the recursion stack.

Key Insights

  • A post-order traversal is essential because we need information from both children before evaluating the current node.
  • The min/max trick (null returns +infinity for min and -infinity for max) elegantly handles leaf nodes without special cases.
  • Valid BST subtrees can be nested — a large BST subtree contains smaller BST subtrees. Each valid BST subtree independently contributes to the total sum.
  • Single-node subtrees are always valid BSTs and always contribute their value to the sum.
  • The problem is about subtrees (contiguous from a root), not arbitrary subsets of nodes.

Edge Cases

  • The entire tree is a valid BST — every subtree is also a valid BST, and each contributes its sum.
  • No subtree larger than a single node is a valid BST — the answer is the sum of all individual node values.
  • The tree is empty — return 0.
  • All node values are the same — depends on whether equality is allowed (typically left children must be strictly less).
  • Negative node values — the algorithm handles them correctly since comparisons work for all integers.

Linked mentions