Maximum Sum BST in Binary Tree - Practice Coding Problems

Maximum Sum BST in Binary Tree - Problem

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.

Input & Output

Example 1 — Mixed Tree

$ Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]

› Output: 20

💡 Note: The maximum sum BST is the subtree rooted at node 3: [3,2,5,null,null,4,6] with sum 3+2+5+4+6 = 20

Example 2 — Invalid Root BST

$ Input: root = [4,3,null,1,2]

› Output: 2

💡 Note: Root is not a valid BST. The maximum sum BST is the single node with value 2, so sum = 2

Example 3 — Negative Values

$ Input: root = [-4,-2,1,1,3,-2,null,-1,null,null,null,2,5,null,null]

› Output: 8

💡 Note: The maximum sum BST is [1,-2,5,2] with sum 1+(-2)+5+2 = 6, but actually the BST [1,null,3] gives sum 4, and BST [5] gives 5, so we need to find the actual maximum

Constraints

The number of nodes in the tree is in the range [1, 4 × 10⁴]
-4 × 10⁴ ≤ Node.val ≤ 4 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with mixed valid/invalid BST subtrees

Identify BSTs

Find all valid BST subtrees and calculate their sums

Maximum Sum

Return the largest sum among all valid BST subtrees

Key Takeaway

🎯 Key Insight: Use single DFS to validate BSTs and track sums simultaneously, avoiding redundant tree traversals

Asked in

a Amazon 15 f Facebook 12 G Google 8

The key insight is to use a single DFS traversal that returns validation status, sum, and bounds together. Each recursive call checks if the current subtree is a valid BST using the returned min/max values from children, avoiding redundant traversals. Best approach is optimized DFS with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS - Single Pass	O(n)	O(n)	Single DFS that validates BST and calculates sum simultaneously
Brute Force - Check Every Subtree	O(n²)	O(n)	For each node, validate if subtree is BST and calculate sum separately

Optimized DFS - Single Pass — Algorithm Steps

Start DFS from root
For each node, recursively process left and right subtrees
Check if current subtree is valid BST using returned min/max bounds
If valid, update global maximum with current sum
Return validation status, sum, and bounds to parent

Visualization

Tap to expand

Step-by-Step Walkthrough

Visit Node

Process left and right subtrees recursively

Check Bounds

Validate BST using returned min/max values

Return State

Return validation, sum, and new bounds

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct Result {
    int isValid;
    int sum;
    int minVal;
    int maxVal;
};

int maxSum = 0;

struct Result dfs(struct TreeNode* node) {
    struct Result result;
    if (!node) {
        result.isValid = 1;
        result.sum = 0;
        result.minVal = INT_MAX;
        result.maxVal = INT_MIN;
        return result;
    }
    
    struct Result left = dfs(node->left);
    struct Result right = dfs(node->right);
    
    if (left.isValid && right.isValid && 
        left.maxVal < node->val && node->val < right.minVal) {
        
        int currentSum = node->val + left.sum + right.sum;
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
        
        result.isValid = 1;
        result.sum = currentSum;
        result.minVal = (left.minVal < node->val) ? left.minVal : node->val;
        result.maxVal = (right.maxVal > node->val) ? right.maxVal : node->val;
        return result;
    } else {
        result.isValid = 0;
        result.sum = 0;
        result.minVal = 0;
        result.maxVal = 0;
        return result;
    }
}

int solution(struct TreeNode* root) {
    maxSum = 0;
    dfs(root);
    return maxSum;
}

struct TreeNode* newNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    struct TreeNode* root = newNode(1);
    root->left = newNode(4);
    root->right = newNode(3);
    root->left->left = newNode(2);
    root->left->right = newNode(4);
    root->right->left = newNode(2);
    root->right->right = newNode(5);
    root->right->right->left = newNode(4);
    root->right->right->right = newNode(6);
    
    printf("%d\n", solution(root));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in the tree

✓ Linear Growth

Space Complexity

O(n)

Recursion call stack depth equals tree height, worst case O(n) for skewed tree

⚡ Linearithmic Space

78.2K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler