1373. Maximum Sum BST in Binary Tree LeetCode Solution

In this guide, you will get 1373. Maximum Sum BST in Binary Tree LeetCode Solution with the best time and space complexity. The solution to Maximum Sum BST in Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Sum BST in Binary Tree solution in C++
4. Maximum Sum BST in Binary Tree solution in Java
5. Maximum Sum BST in Binary Tree solution in Python
6. Additional Resources

Problem Statement of Maximum Sum BST in Binary Tree

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:

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:

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

1373. Maximum Sum BST in Binary Tree LeetCode Solution in C++

struct T {
  bool isBST = false;
  int mx;
  int mn;
  int sum;
};

class Solution {
 public:
  int maxSumBST(TreeNode* root) {
    int ans = 0;
    traverse(root, ans);
    return ans;
  }

 private:
  T traverse(TreeNode* root, int& ans) {
    if (root == nullptr)
      return T(true, INT_MIN, INT_MAX, 0);

    const T left = traverse(root->left, ans);
    const T right = traverse(root->right, ans);

    if (!left.isBST || !right.isBST)
      return T();
    if (root->val <= left.mx || root->val >= right.mn)
      return T();

    // The `root` is a valid BST.
    const int sum = root->val + left.sum + right.sum;
    ans = max(ans, sum);
    return T(true, max(root->val, right.mx), min(root->val, left.mn), sum);
  }
};
/* code provided by PROGIEZ */

1373. Maximum Sum BST in Binary Tree LeetCode Solution in Java

class Solution {
  public int maxSumBST(TreeNode root) {
    traverse(root);
    return ans;
  }

  private record T(boolean isBST, Integer mx, Integer mn, Integer sum) {}

  private int ans = 0;

  private T traverse(TreeNode root) {
    if (root == null)
      return new T(true, Integer.MIN_VALUE, Integer.MAX_VALUE, 0);

    T left = traverse(root.left);
    T right = traverse(root.right);

    if (!left.isBST || !right.isBST)
      return new T(false, null, null, null);
    if (root.val <= left.mx || root.val >= right.mn)
      return new T(false, null, null, null);

    // The `root` is a valid BST.
    final int sum = root.val + left.sum + right.sum;
    ans = Math.max(ans, sum);
    return new T(true, Math.max(root.val, right.mx), Math.min(root.val, left.mn), sum);
  }
}
// code provided by PROGIEZ

1373. Maximum Sum BST in Binary Tree LeetCode Solution in Python

from dataclasses import dataclass


@dataclass
class T:
  isBST: bool | None = False
  mx: int | None = None
  mn: int | None = None
  summ: int | None = None


class Solution:
  def maxSumBST(self, root: TreeNode | None) -> int:
    self.ans = 0

    def traverse(root: TreeNode | None) -> T:
      if not root:
        return T(True, -math.inf, math.inf, 0)

      left: T = traverse(root.left)
      right: T = traverse(root.right)

      if not left.isBST or not right.isBST:
        return T()
      if root.val <= left.mx or root.val >= right.mn:
        return T()

      # The `root` is a valid BST.
      summ = root.val + left.summ + right.summ
      self.ans = max(self.ans, summ)
      return T(True, max(root.val, right.mx), min(root.val, left.mn), summ)

    traverse(root)
    return self.ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.