Skip to content

333. Largest BST Subtree 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
struct T {
  int min;   // the minimum value in the subtree
  int max;   // the maximum value in the subtree
  int size;  // the size of the subtree
};

class Solution {
 public:
  int largestBSTSubtree(TreeNode* root) {
    return dfs(root).size;
  }

 private:
  T dfs(TreeNode* root) {
    if (root == nullptr)
      return {INT_MAX, INT_MIN, 0};

    T l = dfs(root->left);
    T r = dfs(root->right);

    if (l.max < root->val && root->val < r.min)
      return {min(l.min, root->val), max(r.max, root->val),
              1 + l.size + r.size};

    // Mark one as invalid, but still record the size of children.
    // Return (-INF, INF) because no node will be > INT or < -INF.
    return {INT_MIN, INT_MAX, max(l.size, r.size)};
  }
};
 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
class Solution {
  public int largestBSTSubtree(TreeNode root) {
    return dfs(root).size;
  }

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

    T l = dfs(root.left);
    T r = dfs(root.right);

    if (l.max < root.val && root.val < r.min)
      return new T(Math.min(l.min, root.val), Math.max(r.max, root.val), 1 + l.size + r.size);

    // Mark one as invalid, but still record the size of children.
    // Return (-INF, INF) because no node will be > INT or < -INF.
    return new T(Integer.MIN_VALUE, Integer.MAX_VALUE, Math.max(l.size, r.size));
  }

  private record T(int min, // the minimum value in the subtree
                   int max, // the maximum value in the subtree
                   int size // the size of the subtree
  ) {}
}
 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
from dataclasses import dataclass


@dataclass(frozen=True)
class T:
  min: int  # the minimum value in the subtree
  max: int  # the maximum value in the subtree
  size: int  # the size of the subtree


class Solution:
  def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
    def dfs(root: Optional[TreeNode]) -> T:
      if not root:
        return T(math.inf, -math.inf, 0)

      l = dfs(root.left)
      r = dfs(root.right)

      if l.max < root.val < r.min:
        return T(min(l.min, root.val), max(r.max, root.val), 1 + l.size + r.size)

      # Mark one as invalid, but still record the size of children.
      # Return (-inf, inf) because no node will be > inf or < -inf.
      return T(-math.inf, math.inf, max(l.size, r.size))

    return dfs(root).size