Skip to content

1373. Maximum Sum BST in Binary Tree 👍

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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