# Maximum Sum BST in Binary Tree
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-sum-bst-in-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-bst-in-binary-tree
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
**Companies:** [Zepto](https://scaleengineer.com/companies/zepto)
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-sum-bst-in-binary-tree/image0.png)

**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:**

![](https://assets.glich.co/dsa/maximum-sum-bst-in-binary-tree/image1.png)

**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`

# Approaches
## Brute Force: Traverse and Validate
This approach iterates through every node of the binary tree. For each node, it treats the subtree rooted at that node as a potential candidate for the maximum sum BST. Two helper functions are used: one to validate if the subtree is a valid BST, and another to calculate the sum of its nodes if it is.
**Time:** O(N^2) in the worst case (a skewed tree). For each of the N nodes, we might traverse its entire subtree to validate and sum it. In a skewed tree, the sum of subtree sizes is 1 + 2 + ... + N, which is O(N^2). · **Space:** O(N) in the worst case for the recursion stack depth, where N is the number of nodes.
**Pros:** Simple to understand and implement.; Directly translates the problem definition into code.
**Cons:** Highly inefficient due to redundant computations. The `isBST` and `getSum` functions repeatedly traverse the same subtrees for different ancestor nodes.
### Explanation
The main idea is to check every possible subtree. We can perform a traversal (e.g., preorder) on the main tree. For each node visited during this traversal, we check if the subtree rooted at this node is a valid BST. To check for a valid BST, we use a recursive helper function, `isBST(node, min, max)`, which verifies the BST property for every node in the subtree. If the subtree is a valid BST, we use another recursive helper, `getSum(node)`, to calculate the sum of all node values in that subtree. We maintain a global variable, `maxSum`, initialized to 0, and update it whenever we find a valid BST subtree with a sum greater than the current `maxSum`. This process is repeated for all nodes in the tree.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxSum = 0;

    public int maxSumBST(TreeNode root) {
        if (root == null) {
            return 0;
        }
        traverse(root);
        return maxSum;
    }

    private void traverse(TreeNode node) {
        if (node == null) {
            return;
        }
        if (isBST(node, Long.MIN_VALUE, Long.MAX_VALUE)) {
            int sum = getSum(node);
            maxSum = Math.max(maxSum, sum);
        }
        traverse(node.left);
        traverse(node.right);
    }

    private boolean isBST(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }
        if (node.val <= min || node.val >= max) {
            return false;
        }
        return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);
    }

    private int getSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + getSum(node.left) + getSum(node.right);
    }
}
```
### Algorithm
- Initialize a variable `maxSum = 0`.
- Traverse the tree using a function, say `traverse(node)`.
- For each `node` in the traversal:
    - Call a helper function `isBST(node, Long.MIN_VALUE, Long.MAX_VALUE)` to check if the subtree at `node` is a valid BST.
    - If it is a BST, call another helper `getSum(node)` to find its sum.
    - Update `maxSum = Math.max(maxSum, sum)`.
- Recursively call `traverse(node.left)` and `traverse(node.right)`.
- Return `maxSum`.

## Optimal: Single Pass Post-order Traversal
This approach avoids redundant computations by using a single post-order traversal. It works in a bottom-up fashion. For each node, it gathers information from its left and right children to determine if the current subtree is a BST. This information includes whether the child subtrees are BSTs, their min/max values, and their sums.
**Time:** O(N), where N is the number of nodes in the tree. Each node is visited exactly once. · **Space:** O(H), where H is the height of the tree, for the recursion stack. In the worst case of a skewed tree, this is O(N).
**Pros:** Optimal time complexity as it solves the problem in a single pass.; Efficient use of memory, only requiring space for the recursion stack.
**Cons:** More complex to implement and reason about compared to the brute-force approach.; Requires a custom data structure or careful handling of returned values to pass information up the recursion chain.
### Explanation
We can solve this problem efficiently in a single pass using a post-order traversal. The key is to realize that for a node to be the root of a valid BST, its left and right subtrees must also be valid BSTs, and the node's value must be greater than the maximum value in its left subtree and less than the minimum value in its right subtree.

We define a recursive helper function that processes a node and returns a data structure (e.g., a custom class or an array) containing four pieces of information about the subtree rooted at that node:
1. `isBST`: A boolean indicating if the subtree is a valid BST.
2. `minVal`: The minimum value in the subtree.
3. `maxVal`: The maximum value in the subtree.
4. `sum`: The sum of all values in the subtree.

The traversal is post-order because we need to process the children before the parent.

- **Base Case:** For a `null` node, we return values that signify a valid empty BST: `isBST=true`, `minVal=Integer.MAX_VALUE`, `maxVal=Integer.MIN_VALUE`, and `sum=0`. This ensures that any leaf node's parent can form a valid BST with it.
- **Recursive Step:** For a non-null node, we first recursively call the function for its left and right children. Then, using the returned information, we check if the current node can form a BST with its children.

If `left.isBST` and `right.isBST` are true, and `node.val > left.maxVal` and `node.val < right.minVal`, then the current subtree is a valid BST. We calculate its sum (`left.sum + right.sum + node.val`), update our global `maxSum`, and return a new info object for the current subtree.

If the conditions are not met, the current subtree is not a BST. We propagate this information upwards by returning an info object with `isBST=false`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // Using a custom class for clarity to hold information about a subtree.
    class SubtreeInfo {
        boolean isBST;
        int minVal;
        int maxVal;
        int sum;

        SubtreeInfo(boolean isBST, int minVal, int maxVal, int sum) {
            this.isBST = isBST;
            this.minVal = minVal;
            this.maxVal = maxVal;
            this.sum = sum;
        }
    }

    int maxSum = 0;

    public int maxSumBST(TreeNode root) {
        postOrderTraversal(root);
        return maxSum;
    }

    private SubtreeInfo postOrderTraversal(TreeNode node) {
        // Base case: An empty tree is a valid BST with sum 0.
        if (node == null) {
            // minVal is MAX_VALUE and maxVal is MIN_VALUE to handle leaf nodes correctly.
            return new SubtreeInfo(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
        }

        // Recursively get info from left and right subtrees.
        SubtreeInfo leftSubtree = postOrderTraversal(node.left);
        SubtreeInfo rightSubtree = postOrderTraversal(node.right);

        // Check if the current node forms a valid BST.
        if (leftSubtree.isBST && rightSubtree.isBST && node.val > leftSubtree.maxVal && node.val < rightSubtree.minVal) {
            // It's a valid BST.
            int currentSum = node.val + leftSubtree.sum + rightSubtree.sum;
            maxSum = Math.max(maxSum, currentSum);

            // The new min is the minimum of current node's value and left subtree's min.
            int minVal = Math.min(node.val, leftSubtree.minVal);
            // The new max is the maximum of current node's value and right subtree's max.
            int maxVal = Math.max(node.val, rightSubtree.maxVal);
            
            return new SubtreeInfo(true, minVal, maxVal, currentSum);
        } else {
            // It's not a valid BST. Propagate this info up.
            // The values for min, max, and sum don't matter here.
            return new SubtreeInfo(false, 0, 0, 0);
        }
    }
}
```
### Algorithm
- Initialize a global variable `maxSum = 0`.
- Create a recursive helper function `postOrder(node)` that returns an object/array with `[isBST, minVal, maxVal, sum]`.
- **Base Case:** If `node` is `null`, return `[1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0]` (using 1 for true).
- **Recursive Step:**
    - Get info from left and right children: `leftInfo = postOrder(node.left)` and `rightInfo = postOrder(node.right)`.
    - Check if the current subtree is a BST: `leftInfo.isBST` is true AND `rightInfo.isBST` is true AND `node.val > leftInfo.maxVal` AND `node.val < rightInfo.minVal`.
    - **If it is a BST:**
        - Calculate `currentSum = node.val + leftInfo.sum + rightInfo.sum`.
        - Update `maxSum = Math.max(maxSum, currentSum)`.
        - Return a new info object for this valid BST: `[1, Math.min(node.val, leftInfo.minVal), Math.max(node.val, rightInfo.maxVal), currentSum]`.
    - **If it is not a BST:**
        - Return an info object indicating it's not a BST: `[0, 0, 0, 0]`.
- The main function calls `postOrder(root)` and returns `maxSum`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans ; private final int inf = 1 << 30 ; public int maxSumBST ( TreeNode root ) { dfs ( root ); return ans ; } private int [] dfs ( TreeNode root ) { if ( root == null ) { return new int [] { 1 , inf , - inf , 0 }; } var l = dfs ( root . left ); var r = dfs ( root . right ); int v = root . val ; if ( l [ 0 ] == 1 && r [ 0 ] == 1 && l [ 2 ] < v && r [ 1 ] > v ) { int s = v + l [ 3 ] + r [ 3 ]; ans = Math . max ( ans , s ); return new int [] { 1 , Math . min ( l [ 1 ], v ), Math . max ( r [ 2 ], v ), s }; } return new int [ 4 ]; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxSumBST ( TreeNode * root ) { int ans = 0 ; const int inf = 1 << 30 ; function < vector < int > ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) { return vector < int > { 1 , inf , - inf , 0 }; } auto l = dfs ( root -> left ); auto r = dfs ( root -> right ); int v = root -> val ; if ( l [ 0 ] && r [ 0 ] && l [ 2 ] < v && v < r [ 1 ]) { int s = l [ 3 ] + r [ 3 ] + v ; ans = max ( ans , s ); return vector < int > { 1 , min ( l [ 1 ], v ), max ( r [ 2 ], v ), s }; } return vector < int > ( 4 ); }; dfs ( root ); return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def maxSumBST ( self , root : Optional [ TreeNode ]) -> int : def dfs ( root : Optional [ TreeNode ]) -> tuple : if root is None : return 1 , inf , - inf , 0 lbst , lmi , lmx , ls = dfs ( root . left ) rbst , rmi , rmx , rs = dfs ( root . right ) if lbst and rbst and lmx < root . val < rmi : nonlocal ans s = ls + rs + root . val ans = max ( ans , s ) return 1 , min ( lmi , root . val ), max ( rmx , root . val ), s return 0 , 0 , 0 , 0 ans = 0 dfs ( root ) return ans
```